The Heap Data Structure
Heap is a simple but useful data structure that lets you enter a sequence of elements in an arbitrary order, then retrieve them one by one in a sorted order. There are naturally other data structures that can perform the same task, but heap is arguably the simplest, most efficient, and easiest to implement.
Basically, heap is a binary tree with two special properties:
- Heap property. The value of each node is smaller than those of its sons. This effectively implies that the root element is the smallest one, so it can be readily accessed in O(1). On the other hand, finding the largest element is inefficient. It must reside in one of the leaves of the tree (because if it had a child, it would not be the largest one), but to find it, you must painstakingly scan all the leaves.
- Tree property. Heap is an almost complete binary tree; that is, all the elements up to a certain depth are present in the tree, except maybe for some elements at the lower-most level (see Figure 1). The maximum depth of the heap tree is log2n, where n is the total number of nodes. Consequently, you don't need to use a tree to actually implement a heap; an array (or a vector) will do. This way, for a node residing at index i, its two sons reside at indices 2*i+1 and 2*i+2, while its parent resides at (i-1)/2.
When a heap is embedded in an array, you can define its last element as the very last element of the host array. This element can be safely removed from the heap without disturbing any of its properties. This tactic is what lets you efficiently extract the smallest element from the heap—you simply remove the last element from the heap, inject it in place of the smallest element (at the root), and bubble it down, restoring the heap property for every node it encounters en route; see Figure 2. The time complexity of this operation is bounded by the tree depth and equals O(logn).
To insert a new element into the heap, you just insert it after the last array element and bubble it up similarly to restore the heap property. The complexity of this operation is also O(logn).
Finally, an unsorted array can be converted into a heap ("heapified") by performing the bubble operations in a particular sequence. Interestingly, while the worst-case complexity of any given bubble operation is O(logn), all the operations required for heapification together sum up to only O(n)!
And the best news is that you don't even need to implement any of the heap manipulation functions, as they constitute an integral part of the C++ Standard Library. The three heap operations described here are realized by the STL functions std::pop_heap, std::push_heap, and std::make_heap, defined in the header file <algorithm>.
—E.G. and A.G.
