[ADT] Priority Queue Abstract Data Type

Priority Queue ADT

A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.

The priority queue enqueue operation inserts an item such that the item is closer to the front thatn all items of lower priority, and closer to the end than all items of equal or higher priority.

The priority queue dequeue operation removes and returns the item at the front of the queue, which has the highest priority. 

 

In addition to enqueue and dequeue, a priority queue usually supports peeking and length querying. 

A peek operation returns the highest priority item, without removing the item from the front of the queue. 

 

Some Common Operations

 

 

---

Enqueueing items with priority

A priority queue can be implemented such that each item's priority can be determined from the item itself. 

Ex. A customer object may contain information about a customer, including the customer's name and a service priority number. In this case, the priority resides within the object. 

 

A priority queue may also be implemented such that all properties are specified during a call to EnqueueWithPriority: An enqueue opeariton that includes an argument for the enqueued item's priority.

In the followingf example, the priority doesn't reside within the object, but still act as a dependent priority variable for each object. 

 

---

Implementing Priority Queues with Heaps

A priority queue is commonly implemented using a heap.

A heap will keep the highest priority item in the root node and allow access in O(1) time.

Adding and removing items from teh queue will operate in worst-case O(logN) time.