Heap (data structure)

Lore & Background

The heap data structure, specifically the binary heap, was introduced by J. W. J. A common implementation is the binary heap, where the tree is a complete binary tree. Heaps are typically constructed in-place in the same array where elements are stored, with structure implicit in the access pattern of operations, requiring no additional memory beyond that used for storing keys. The heap has the smallest possible height when a complete binary tree: a heap with N nodes and a branches per node always has log_a N height.

Reader's Guide

Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm and Prim's minimal-spanning-tree algorithm, reducing run time by polynomial order. They are used in heapsort, one of the best sorting methods being in-place and with no quadratic worst-case scenarios. Heaps enable selection algorithms, allowing access to the smallest or largest element in constant time, and finding the k-smallest element in O(k) time. They are also useful for K-way merge operations, merging many already-sorted input streams into a single sorted output stream. The C++ Standard Library provides make_heap, push_heap, and pop_heap algorithms for heaps, usually implemented as binary heaps, operating on arbitrary random access iterators. The heap data structure has many applications including priority queues, external sorting, and streaming results from distributed data such as a log structured merge tree.

Did You Know?

• In a heap, the highest or lowest priority element is always stored at the root.
• Heaps are typically constructed in-place in the same array where elements are stored, requiring no additional memory beyond that used for storing keys.
• A heap with N nodes and a branches for each node always has log_a N height.