Class: Containers::PriorityQueue
- Inherits:
-
Object
- Object
- Containers::PriorityQueue
- Includes:
- Enumerable
- 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
16 17 18 19 20 |
# 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 |
Instance Method Details
#clear ⇒ Object
Clears all the items in the queue.
43 44 45 |
# File 'lib/containers/priority_queue.rb', line 43 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
109 110 111 |
# File 'lib/containers/priority_queue.rb', line 109 def delete(priority) @heap.delete(priority) end |
#empty? ⇒ Boolean
Returns true if the queue is empty, false otherwise.
48 49 50 |
# File 'lib/containers/priority_queue.rb', line 48 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
62 63 64 |
# File 'lib/containers/priority_queue.rb', line 62 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"
76 77 78 |
# File 'lib/containers/priority_queue.rb', line 76 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
91 92 93 |
# File 'lib/containers/priority_queue.rb', line 91 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"
38 39 40 |
# File 'lib/containers/priority_queue.rb', line 38 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
28 29 30 |
# File 'lib/containers/priority_queue.rb', line 28 def size @heap.size end |