Heap (data structure)
Tree-based data structure satisfying the heap property.
A heap is a tree-based data structure in computer science that adheres to a specific ordering rule known as the heap property. In a max heap, for any given node, the key of its parent node is always greater than or equal to the key of the child node. Conversely, in a min heap, the parent's key is less than or equal to the child's key. The topmost node, which has no parent, is called the root. This structure is a highly efficient implementation of the abstract data type known as a priority queue, and the term "heap" is often used interchangeably with priority queue regardless of the underlying implementation. The highest-priority element in a max heap, or the lowest in a min heap, is always stored at the root. However, a heap is not a fully sorted structure; it is only partially ordered, meaning there is no implied ordering between sibling nodes or cousins. This makes it particularly useful when the primary operations involve repeatedly removing the element with the highest or lowest priority, or when insertions are interleaved with root removals.
The binary heap, a common implementation where the tree is a complete binary tree, was introduced by J. W. J. Williams in 1964 as a data structure for the heapsort sorting algorithm. Heaps are also crucial in efficient graph algorithms, such as Dijkstra’s algorithm. When a heap is a complete binary tree, it achieves the smallest possible height; a heap with N nodes and a branches per node will always have a height of log base a of N. Heaps are typically constructed in-place within the same array used to store the elements, with the tree structure being implicit in the array’s access pattern. This differs from other data structures that may require additional memory beyond that used for storing the keys. Common operations include finding the maximum or minimum (peek), inserting a new key (push), extracting the root (pop), and replacing the root with a new key, which is more efficient than a separate pop and push because it requires only one rebalancing step. Other operations include creating an empty heap, building a heap from an array (heapify), merging two heaps, and internal operations like sift-up and sift-down to restore the heap property after insertions or deletions.
- field
- Computer science
- known_for
- Heap data structure, binary heap, heapsort algorithm
Lore & Background
The heap is a tree-based data structure where each node holds a key, and the structure satisfies the heap property: in a max-heap, every parent node’s key is greater than or equal to its children’s keys, while in a min-heap, each parent’s key is less than or equal to its children’s keys. The topmost node, which has no parent, is called the root. A common implementation is the binary heap, in which the tree is a complete binary tree, giving it the smallest possible height—a heap with N nodes and a branches per node always has a height of log_a N. Heaps are typically constructed in-place in the same array where elements are stored, with their structure implicit in the access pattern of operations, requiring no additional memory beyond that used for storing keys. This contrasts with other data structures that may need extra memory for similar theoretical bounds. The heap data structure, specifically the binary heap, was introduced by J. W. J. Williams in 1964 as a data structure for the heapsort sorting algorithm. Heaps are also crucial in efficient graph algorithms such as Dijkstra’s algorithm. A heap is not a sorted structure but is partially ordered; there is no implied ordering between sibling or cousin nodes, and no sequence is implied for an in-order traversal. The maximum number of children each node can have depends on the heap type. In an array-based binary heap, the root is at the first index, its children at indices 2i and 2i+1 (for 1-indexed arrays), and its parent at floor(i/2). Balancing is done via sift-up (moving a node up the tree) or sift-down (moving a node down) operations, swapping out-of-order elements to restore the heap property after insertion, deletion, or replacement.
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.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record