Introduction to Priority Queues

Many applications require a special type of queuing in which items are pushed onto the queue by order of arrival, but removed from the queue based on some other priority scheme. A priority scheme might be based on the item’s level of importance for example. The goal in this book is to investigate efficient data structures for storing data in this fashion and understand the underlying concepts and the time and space complexity of this structure and its algorithms.

Priority Queue

A priority queue is data structure similar to a regular queue with one difference: each element has an additional priority attached to it. In a priority queue, an element with high priority is served before an element with low priority.

Priority Queues vs Heaps

Priority queues are typically implemented with heaps, although the two are fundamentally different topics. A priority queue is similar to an list or a map in that it may be implemented using a heap or a number of different techniques such as an unordered array, just as a list can be built using a linked list or an array.

Priority Queue Operations

A priority queue supports the following operations:

• IsEmpty: Determines whether the queue is empty.
• Insert(Priority): Inserts a new element into the queue with a priority.
• Pull/Pop/GetMaximum: Removes the element with the highest priority from the queue and return. This is also known as “get minimum element”.
• (Optional) Peek: Returns the highest-priority element but does not affect the queue. It has O(1) performance.

Priority Queues in Programming Languages

• Java comes with a built-in PriorityQueue collection. For more information, see this tutorial on how to use priority queues in Java.
• PriorityQueue in C# link