Class: DSA::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/DSA/priority_queue.rb

Overview

priority queue built on top of array based heap

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



11
12
13
 
# File 'lib/DSA/priority_queue.rb', line 11

def initialize
  @data = Array.new
end

Instance Method Details

#add(priority, element) ⇒ Object

priority is a number, the smaller it is, higher it has a priority



26
27
28
29
 
# File 'lib/DSA/priority_queue.rb', line 26

def add(priority, element)
  @data.push PriorityQueueNode.new(priority,element)
  up_heap_bubbling length-1
end

#length ⇒ Object 



15
16
17
 
# File 'lib/DSA/priority_queue.rb', line 15

def length
  @data.length
end

#pop ⇒ Object

remove the top and return the element



32
33
34
35
36
37
 
# File 'lib/DSA/priority_queue.rb', line 32

def pop
  value = top
  @data[0] = @data.pop # move the rightmost node to the top
  down_heap_sinking 0
  value
end

#top ⇒ Object

get the value of the top without removing it



20
21
22
23
 
# File 'lib/DSA/priority_queue.rb', line 20

def top
  return nil if length == 0
  @data.first.element
end