Priority Queues

Priority queue data structure is an abstract data type that provides a way to maintain a set of elements, each with an associated value called key.

There are two kinds of priority queues: a maxpriority queue and a minpriority queue. In both kinds, the priority queue stores a collection of elements and is always able to provide the most “extreme” element, which is the only way to interact with the priority queue. For the remainder of this section, we will discuss maxpriority queues. Minpriority queues are analogous.
Operations

A maxpriority queue provides the following operations:

insert: add an element to the priority queue.

maxElement: return the largest element in the priority queue.

removeMaxElement: remove the largest element from the priority queue.


A maxpriority queue can also provide these additional operations:

size: return the number of elements in the priority queue.

increaseKey: updates the key of an element to a larger value.

updatePriorities: assume the values of the keys have been changed and reorder the internal state of the priority queue.


The names of these methods may be different based on implementations, but all priority queues should provide a way to do these or similar operations.
Implementations

Let’s explore several possibilities for data structures we could use to implement a priority queue:

Unordered array
A simple, yet inefficient implementation, as retrieving the max element would require searching the entire array.

Sorted array
This is not a very efficient implementation either. Inserting a new element requires linearly searching the array for the correct position. Removing similarly requires a linear time: the rest of the elements need to be adjusted (shifted) into correct positions.

Hash table
Although inserting into a hash table takes constant time (given a good hash function), finding the max element takes linear time. Therefore, this would be a poor choice for the underlying data structure.

Heap
It turns out that that a heap makes an efficient priority queue.


Below is a summary of the complexities of the common operations on a priority queue:
Operation Unordered array Sorted array Hash table Binary heap insert
$\Theta(1)$
$\Theta(N)$
$\Theta(1)$
$\Theta(\log (N))$
maxElement
$\Theta(N)$
$\Theta(1)$
$\Theta(N)$
$\Theta(1)$
removeMaxElement
$\Theta(N)$
$\Theta(1)$
$\Theta(N)$
$\Theta(\log (N))$