Heaps and priority queues

Priority queue

A priority queue is a queue in which each element is assigned a priority. The priority queue ADT has insert, removeMin and min methods for insertion, removing the item with the lowest priority and accessing the item with the lowest priority respectively. Priority queues can be used for sorting by inserting elements with priority equal to value and then removing.

Heap

A heap is a binary tree which stores keys and satisfies the heap-order property. The heap-order property states that every child node is less than or equal to it's parent. The first node in a heap is the root and the last node is the rightmost node of maximum depth. A heap storing $n$ items has height $O(\log n)$.

A priority queue can be implemented using a heap. Each node has the priority as a key where a smaller key means a higher priority and the root node holds the highest priority key.

An item can be inserted into a priority queue heap in the deepest, rightmost part of the heap. The heap order can then be restored using the upheap algorithm. This swaps the new node with its parent until it is smaller than its parent. This runs in $O(\log n)$.

The highest priority item will be the root. When the root is removed, the root is replaced with downheap algorithm. The largest child of a node is swapped with it until it is larger than all of its children.

A heap-based priority sort has run time $O(n \log n)$ because it needs $n$ calls of $O(\log n)$ for each insertion and $n$ calls of removeMin which takes $O(\log n)$ each.