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:
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.
Back to Article