Heap
A heap is a specialized tree-based data structure that satisfies the heap property: in a min-heap, every parent node is less than or equal to its children; in a max-heap, every parent is greater than or equal to its children. Heaps are…
Definition
A heap is a specialized tree-based data structure that satisfies the heap property: in a min-heap, every parent node is less than or equal to its children; in a max-heap, every parent is greater than or equal to its children. Heaps are typically implemented as arrays representing a complete binary tree, and they efficiently support retrieving the minimum or maximum element in O(1) and inserting or removing it in O(log n).
Overview
A heap maintains a partial order — unlike a binary search tree, it does not guarantee full sorted order, only that each parent satisfies the heap property relative to its children. This weaker guarantee is exactly what makes heaps fast: the root is always the min (or max) element, accessible in constant time, while insertion and extraction only need to restore the heap property along a single path from root to leaf, achieving O(log n). Heaps are almost always implemented as arrays rather than linked node structures, exploiting the fact that a complete binary tree can be stored compactly: for a node at index i, its children live at indices 2i+1 and 2i+2 (0-indexed), avoiding pointer overhead. Insertion appends a new element and 'bubbles up' by swapping with its parent until the heap property is restored; extraction removes the root, moves the last element to the root position, and 'sifts down' until the property holds again. The most common application is the priority queue: a queue where elements are dequeued by priority rather than insertion order, used in algorithms like Dijkstra's shortest path, Prim's minimum spanning tree, and task schedulers. Heapsort uses a heap to sort an array in-place in O(n log n) time, and heaps are used to efficiently solve top-k / k-th largest element problems without fully sorting a dataset. Because a heap only guarantees ordering between parent and child (not siblings or across levels), it cannot support efficient arbitrary search — finding a specific element requires O(n) in the worst case, which is the key trade-off compared to a balanced binary search tree.
Key Concepts
- Satisfies heap property: parent ≤ children (min-heap) or parent ≥ children (max-heap)
- Implemented as an array representing a complete binary tree
- O(1) access to minimum or maximum element at the root
- O(log n) insertion and extraction via bubble-up / sift-down
- Backbone of the priority queue abstract data type
- Only guarantees parent-child order, not full sorted order
- Used in heapsort for O(n log n) in-place sorting