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.
Included modules
- Enumerable
Public Class methods
Create a new, empty PriorityQueue
# File lib/containers/priority_queue.rb, line 16 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
Public Instance methods
Clears all the items in the queue.
# File lib/containers/priority_queue.rb, line 43 def clear @heap.clear end
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
# File lib/containers/priority_queue.rb, line 109 def delete(priority) @heap.delete(priority) end
Returns true if the queue is empty, false otherwise.
# File lib/containers/priority_queue.rb, line 48 def empty? @heap.empty? end
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
# File lib/containers/priority_queue.rb, line 62 def has_priority?(priority) @heap.has_key?(priority) end
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"
# File lib/containers/priority_queue.rb, line 76 def next @heap.next end
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
# File lib/containers/priority_queue.rb, line 91 def pop @heap.pop end
Add an object to the queue with associated priority.
q = Containers::PriorityQueue.new q.push("Alaska", 1) q.pop #=> "Alaska"
# File lib/containers/priority_queue.rb, line 38 def push(object, priority) @heap.push(priority, object) end
Returns the number of elements in the queue.
q = Containers::PriorityQueue.new q.size #=> 0 q.push("Alaska", 1) q.size #=> 1
# File lib/containers/priority_queue.rb, line 28 def size @heap.size end