A treatment of binary heaps and their use in other data structures.

Binary heaps are used in many other important data structures and algorithms. For example, they are often used as implementations of priority queues, because the items they store are sorted. And as priority queues are central to many other important algorithms--such as Dijkstra's algorithm for discovering the shortest path between two nodes in a graph--they can help us understand how these more complex algorithms work.

A binary heap is a binary tree with two important properties. First, it is complete: this means that every level of the tree is filled with the possible exception of the lowest level, which is filled from left to right. Second, the parents and children of the tree are ordered by a relation R such that if i is the parent of j, R(i, j).

The second property is known as the heap property, and it's rather abstract, so a couple of examples may help make it clear.

Suppose we have a bunch of numbers and want to always pull out the largest number from the bunch. Then if i and j are stored in the heap and i is the parent of j, i cannot be less than j.

Or suppose we have items from a grocery store and always want the cheapest item to be the first item available. Then if i and j are items in the heap and i is the parent of j, then i cannot be more expensive than j.

Or perhaps we have color samples and we want to always get the darkest sample in the bunch. Then i cannot to be lighter than j if i is j's parent.

These examples show it doesn't matter what you're ordering or what particular order you care about--you can order those things using a binary heap.

The examples above illustrated uses of a priority queue. A priority queue isn't a queue, precisely--queues are structures wherein the order of retrieval is identical to the order of insertion--although queues are special cases of priority queues (the ordering relation would be earlier insertion). Priority queues are defined with an ordering relation, and their items can be retrieved in that order.

As you may imagine, it's also possible to sort using a binary heap. Create a binary heap whose ordering relation is the one you would use to sort the items, put the items into the heap, then extract them from the heap until it is empty; the result is a list of items in the proper order.

Binary heaps are efficient data structures. Priority queues can be created in O(n log n) time (on par with the most efficient sorting algorithms), and extracting the first item can be done in O(log n) time.