Class: PriorityQueue

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

Overview

Array-based PriorityQueue implementation

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



3
4
5
 
# File 'lib/priority_queue.rb', line 3

def initialize
  clear
end

Instance Method Details

#<<(element) ⇒ Object Also known as: push

Push element onto the priority queue.



8
9
10
11
12
 
# File 'lib/priority_queue.rb', line 8

def <<(element)
  @elements << element
  # bubble up the element that we just added
  bubble_up(@elements.size - 1)
end

#clear ⇒ Object

Reset the priority queue to empty.



33
34
35
 
# File 'lib/priority_queue.rb', line 33

def clear
  @elements = [nil]
end

#empty? ⇒ Boolean

Return a boolean indicating whether the queue is empty or not

Returns:

  • (Boolean) 


38
39
40
 
# File 'lib/priority_queue.rb', line 38

def empty?
  @elements.length < 2
end

#peek ⇒ Object

Inspect the element at the head of the queue.



17
18
19
20
 
# File 'lib/priority_queue.rb', line 17

def peek
  # the first element will always be the min, because of the heap constraint
  @elements[1]
end

#pop ⇒ Object

Remove and return the next element from the queue, determined by priority.



23
24
25
26
27
28
29
30
 
# File 'lib/priority_queue.rb', line 23

def pop
  # remove the last element of the list
  min = @elements[1]

  # and make sure the tree is ordered again
  bubble_down(1) unless empty?
  min
end