# Class: Containers::PriorityQueue

Inherits:
Object
• Object
show all
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

• Clears all the items in the queue.

• call-seq: delete(priority) -> object delete(priority) -> nil.

• Returns true if the queue is empty, false otherwise.

• call-seq: has_priority? priority -> boolean Return true if the priority is in the queue, false otherwise.

• constructor

Create a new, empty PriorityQueue.

• call-seq: next -> object.

• #pop ⇒ Object (also: #next!)

call-seq: pop -> 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("Delaware", 30)
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.

Returns:

• (Boolean)
 ``` 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.has_priority?(1)    #=> true
q.has_priority?(2)    #=> false
``````

Returns:

• (Boolean)
 ``` 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("Delaware", 30)
q.push("Georgia", 35)
``````
 ``` 76 77 78``` ```# File 'lib/containers/priority_queue.rb', line 76 def next @heap.next end```

### #pop ⇒ ObjectAlso 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("Delaware", 30)
q.push("Georgia", 35)
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
 ``` 38 39 40``` ```# File 'lib/containers/priority_queue.rb', line 38 def push(object, priority) @heap.push(priority, object) end```
``````q = Containers::PriorityQueue.new
 ``` 28 29 30``` ```# File 'lib/containers/priority_queue.rb', line 28 def size @heap.size end```