A priority queue is a structure that maintains an order of some description (usually ascending or descending numerical order) and allows two operations:
The most common method for implementing a priority queue is a structure called a heap, which is implemented using a leftist BinaryTree. The heap condition states that a parent must be smaller (in this example) than both its children.
For example
5
/ \
7 6
/ \ / \
15 20 40 10
This is a well-formed heap. (Every parent is smaller than both its children. Relations with siblings are irrelevant. The smallest value in the heap is always the root.
When items are added to the tree, we add to the next available space in the heap and then perform an upheap operation; this swaps them with their parent if they are smaller. This way, a value that is smaller than the smallest value will propogate to the top of the heap, ready to be removed.
To remove an item, it is swapped with the last item in the heap, the length of the heap is shortened by one, and a downheap operation is performed on the root, swapping it with the smallest of its children until the heap condition is satisfied (and the smallest node is at the root again.) You can then access the item by grabbing the (size) item in the heap.
A great property of the heap is that it can be condensed into an array: if the root is stored at position 1 of an array, the children of any node n are at positions 2n and 2n+1:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 5 | 7 | 6 | 15 | 20 | 40 | 10
(It is common to store the number of items in the heap at position 0.) The children of the root (node 1) are at 2*1 (2) and 2*1+1 (3); the children of node 3 are at positions 2*3 (6) and 2*3+1 (7) etc. This condition holds for any entry in the heap.
An excellent application for a priority queue is Replacement Selection for external sorting.
No page links to PriorityQueue.
