Class: Containers::PriorityQueue
- Inherits:
-
Object
- Object
- Containers::PriorityQueue
- Defined in:
- lib/containers/priority_queue.rb
Overview
A Priority Queue is a data structure that behaves like a queue except that elements have an
associated priority. The #next and #pop methods return the item with the next highest priority.
Priority Queues are often used in graph problems, such as Dijkstra's Algorithm for shortest
path, and the A* search algorithm for shortest path.
This container is implemented using the Fibonacci heap included in the Collections library.
Instance Method Summary collapse
-
#clear ⇒ Object
Clears all the items in the queue.
-
#delete(priority) ⇒ Object
call-seq: delete(priority) -> object delete(priority) -> nil.
-
#empty? ⇒ Boolean
Returns true if the queue is empty, false otherwise.
-
#has_priority?(priority) ⇒ Boolean
call-seq: has_priority? priority -> boolean Return true if the priority is in the queue, false otherwise.
-
#initialize(&block) ⇒ PriorityQueue
constructor
Create a new, empty PriorityQueue.
-
#next ⇒ Object
call-seq: next -> object.
-
#pop ⇒ Object
(also: #next!)
call-seq: pop -> object.
-
#push(object, priority) ⇒ Object
Add an object to the queue with associated priority.
-
#size ⇒ Object
(also: #length)
Returns the number of elements in the queue.
Constructor Details
#initialize(&block) ⇒ PriorityQueue
Create a new, empty PriorityQueue
15 16 17 18 19 |
# File 'lib/containers/priority_queue.rb', line 15 def initialize(&block) # We default to a priority queue that returns the largest value block ||= lambda { |x, y| (x <=> y) == 1 } @heap = Containers::Heap.new(&block) end |
Instance Method Details
#clear ⇒ Object
Clears all the items in the queue.
42 43 44 |
# File 'lib/containers/priority_queue.rb', line 42 def clear @heap.clear end |
#delete(priority) ⇒ Object
call-seq:
delete(priority) -> object
delete(priority) -> nil
Delete an object with specified priority from the queue. If there are duplicates, an arbitrary object with that priority is deleted and returned. Returns nil if there are no objects with the priority.
q = PriorityQueue.new
q.push("Alaska", 50)
q.push("Delaware", 30)
q.delete(50) #=> "Alaska"
q.delete(10) #=> nil
108 109 110 |
# File 'lib/containers/priority_queue.rb', line 108 def delete(priority) @heap.delete(priority) end |
#empty? ⇒ Boolean
Returns true if the queue is empty, false otherwise.
47 48 49 |
# File 'lib/containers/priority_queue.rb', line 47 def empty? @heap.empty? end |
#has_priority?(priority) ⇒ Boolean
call-seq:
has_priority? priority -> boolean
Return true if the priority is in the queue, false otherwise.
q = PriorityQueue.new
q.push("Alaska", 1)
q.has_priority?(1) #=> true
q.has_priority?(2) #=> false
61 62 63 |
# File 'lib/containers/priority_queue.rb', line 61 def has_priority?(priority) @heap.has_key?(priority) end |
#next ⇒ Object
call-seq:
next -> object
Return the object with the next highest priority, but does not remove it
q = Containers::PriorityQueue.new
q.push("Alaska", 50)
q.push("Delaware", 30)
q.push("Georgia", 35)
q.next #=> "Alaska"
75 76 77 |
# File 'lib/containers/priority_queue.rb', line 75 def next @heap.next end |
#pop ⇒ Object Also known as: next!
call-seq:
pop -> object
Return the object with the next highest priority and removes it from the queue
q = Containers::PriorityQueue.new
q.push("Alaska", 50)
q.push("Delaware", 30)
q.push("Georgia", 35)
q.pop #=> "Alaska"
q.size #=> 2
90 91 92 |
# File 'lib/containers/priority_queue.rb', line 90 def pop @heap.pop end |
#push(object, priority) ⇒ Object
Add an object to the queue with associated priority.
q = Containers::PriorityQueue.new
q.push("Alaska", 1)
q.pop #=> "Alaska"
37 38 39 |
# File 'lib/containers/priority_queue.rb', line 37 def push(object, priority) @heap.push(priority, object) end |
#size ⇒ Object Also known as: length
Returns the number of elements in the queue.
q = Containers::PriorityQueue.new
q.size #=> 0
q.push("Alaska", 1)
q.size #=> 1
27 28 29 |
# File 'lib/containers/priority_queue.rb', line 27 def size @heap.size end |