A priority queue is a collection data type similar to a queue or stack except that elements are removed by their priority (either the largest or smallest depending on the implementation). Queues define two main operations:

• Insert: which adds an element with an associated priority to the collection.
• Extract Maximum/Minimum Removes the highest or lowest priority element depending on implementation and returns it.

Typically for a single priority queue implementation it will only implement either extract maximum or extract minimum but not both.

Abstract Data Type

template <class T>
class PriorityQueue {
	public:
		PriorityQueue();
	
		// Insert an element with associated priority
		void insert(const T& element);
		
		// Remove and return the highest priority element
		T extractMax();
		
		// Return the highest priority element without removing
		T peek();
}

Implementation

Binary Heap

A binary heap provides an efficient implementation of a priority queue. Elements are stored in a complete binary tree structure that maintains the heap property where each parent node has a priority greater than (max heap) or less than (min heap) its children.

Using a binary heap both insert and extract maximum/minimum operations can be performed in time. The peek operation runs in time as it simply returns the root element without modification.

The heap is typically stored using an array representation where for an element at index the left child is at index and the right child is at index , allowing for efficient traversal without explicit pointers.