Heap — A Complete Binary Tree with an Order Property
A heap is a complete binary tree stored as an array, with one rule: every parent is either
greater than or equal to its children (max-heap) or less than or equal to its children (min-heap).
This single constraint — the heap property — enables O(log n) insert and delete, and O(1) access to the
maximum or minimum element. These three operations together make the heap the most efficient implementation
of a priority queue, and the foundation of the Heap Sort algorithm.
The Structure
Complete Binary Tree Stored as an Array
A heap is always a complete binary tree — every level is fully filled except possibly the last, which is filled from left to right. This completeness property is not just aesthetic: it guarantees the tree height is always ⌊log₂ n⌋, which is what gives heap operations their O(log n) guarantee.
Rather than using linked nodes with pointers, a heap is stored as a plain array. The root is at index 0, its children at indices 1 and 2, their children at 3, 4, 5, 6, and so on. The parent-child relationship is captured entirely by arithmetic — no pointer is needed at all.
Max-Heap: every parent ≥ its children
The same heap stored as an array — indices 0 to 6
90[0] root
80[1]
70[2]
40[3]
30[4]
60[5]
50[6]
Parent-child index formulas — all O(1)
Parent of node at index i = ⌊(i − 1) / 2⌋
Left child of index i = 2i + 1
Right child of index i = 2i + 2
Example: node at index 1 (value 80)
Parent: ⌊(1−1)/2⌋ = 0 → arr[0] = 90 ✓
Left child: 2×1+1 = 3 → arr[3] = 40 ✓
Right child: 2×1+2 = 4 → arr[4] = 30 ✓
Why use an array instead of linked nodes? With pointers, finding the parent of a node requires storing an extra PARENT pointer in every node — 33% more memory per node. With the array formula, the parent is found in O(1) by arithmetic alone. This is why heaps use arrays, and why the completeness property must be maintained — a gap in the array would break the formula.
Two Variants
Max-Heap and Min-Heap
The heap property comes in two flavours depending on whether the largest or smallest element should always be at the root.
🔺
Max-Heap
Every parent is greater than or equal to both its children. The root always holds the maximum element of the entire heap.
Used for: finding the minimum quickly, Dijkstra's shortest path, Huffman encoding, implementing a min-priority queue.
Switching between min and max: Converting a max-heap algorithm to min-heap simply requires reversing all comparisons. The structure, complexity, and all formulas remain identical. Most library implementations (Java PriorityQueue, Python heapq) implement min-heap by default.
Core Operation
Heapify — Restoring the Heap Property
Heapify is the fundamental operation that fixes a violation of the heap property at a single node. It is used after every insertion and deletion. There are two directions — sift-up (also called bubble-up) after insertion, and sift-down (also called heapify-down) after deletion.
⬆️
Sift-Up (after Insert)
When a new element is inserted, it is placed at the next available position (end of the array). If it violates the heap property with its parent, swap them. Continue comparing with the new parent and swapping upward until the property is restored or the root is reached.
At most ⌊log₂ n⌋ swaps — one per level. O(log n)
⬇️
Sift-Down (after Delete)
When the root is removed (the only correct deletion point), the last element is moved to the root. If it violates the heap property with its children, swap it with the larger child (max-heap) or smaller child (min-heap). Continue downward until the property is restored or a leaf is reached.
At most ⌊log₂ n⌋ swaps. O(log n)
Insert 95 into the max-heap — sift-up trace
Step 1: Place 95 at index 7 (next available). Array: [90, 80, 70, 40, 30, 60, 50, 95] Step 2: Parent of index 7 = ⌊(7−1)/2⌋ = 3 → arr[3] = 40. Is 95 > 40? Yes → swap.
Array: [90, 80, 70, 95, 30, 60, 50, 40] Step 3: Now at index 3. Parent = ⌊(3−1)/2⌋ = 1 → arr[1] = 80. Is 95 > 80? Yes → swap.
Array: [90, 95, 70, 80, 30, 60, 50, 40] Step 4: Now at index 1. Parent = ⌊(1−1)/2⌋ = 0 → arr[0] = 90. Is 95 > 90? Yes → swap.
Array: [95, 90, 70, 80, 30, 60, 50, 40] At root — stop. 3 swaps. Heap property restored.
// Sift-Down for max-heap (used after deletion)function siftDown(arr, i, n):
largest = i
left = 2*i + 1
right = 2*i + 2if left < n and arr[left] > arr[largest]: largest = left
if right < n and arr[right] > arr[largest]: largest = right
if largest ≠ i:
swap(arr[i], arr[largest])
siftDown(arr, largest, n) // recurse downward
Primary Application
Priority Queue — Serve the Most Important First
A priority queue is an abstract data type where each element has a priority and dequeue always removes the element with the highest priority — regardless of arrival order. A heap is the most efficient concrete implementation of a priority queue.
➕
Insert with Priority
Add the element at the end of the array, then sift-up to restore the heap property. The element settles at the correct position based on its priority value. O(log n)
🏆
Get Highest Priority
The root always holds the highest-priority element (max-heap) or lowest-cost element (min-heap). Reading it requires no traversal — just return arr[0]. O(1)
⬅️
Remove Highest Priority
Swap root with the last element, reduce heap size by 1, then sift-down from the root to restore the heap property. O(log n)
🔨
Build Heap from Array
Start from the last non-leaf node ⌊n/2⌋−1 and sift-down each node up to the root. Despite doing n/2 sift-down operations, the total cost is O(n) — not O(n log n). This is the key insight behind Heap Sort's efficiency.
Why O(n) to build a heap? Sift-down at depth d costs at most (height − d) operations. Most nodes are near the bottom where the cost is small. The mathematical sum ∑ n/2^k · k = O(n) — the total work is linear even though there are n/2 non-leaf nodes each needing sift-down.
Sorting Algorithm
Heap Sort — O(n log n) In-Place Sorting
Heap Sort uses a max-heap to sort an array in ascending order. It is one of the few sorting algorithms that is simultaneously O(n log n) worst case, O(1) auxiliary space, and not dependent on input order.
// Heap Sort — ascending order using max-heapfunction heapSort(arr, n):
// Phase 1: Build max-heap from the array — O(n)for i = ⌊n/2⌋ - 1 down to 0:
siftDown(arr, i, n)
// Phase 2: Extract max one by one — O(n log n)for i = n-1 down to 1:
swap(arr[0], arr[i]) // move current max to end
siftDown(arr, 0, i) // restore heap on remaining elements
Heap Sort vs Quick Sort vs Merge Sort: Heap Sort guarantees O(n log n) in all cases (Quick Sort degrades to O(n²) on sorted input) and uses O(1) auxiliary space (Merge Sort needs O(n) extra space). However, Quick Sort is faster in practice due to better cache locality — the heap's sift-down jumps across distant array indices, causing frequent cache misses. Heap Sort is chosen when worst-case guarantees and in-place sorting are both required.
Applications
Where Heaps Are Used
🗺️
Dijkstra's Shortest Path Algorithm
Dijkstra's algorithm finds the shortest path in a weighted graph by always processing the unvisited vertex with the smallest known distance first. A min-heap (priority queue) stores vertices keyed by their current distance. Each extraction is O(log V) and each relaxation (distance update) is O(log V), giving the overall algorithm O((V + E) log V) with a heap — far better than O(V²) with a plain array.
🌳
Huffman Encoding (Data Compression)
Huffman encoding assigns shorter binary codes to more frequent characters, achieving lossless data compression. The algorithm uses a min-heap to always merge the two lowest-frequency symbols first. Each merge operation takes O(log n) with a heap. The resulting Huffman tree gives the optimal prefix-free code, reducing file sizes by 20–90% depending on character frequency distribution. Used in ZIP, JPEG, and MP3 formats.
🖥️
Operating System Task Scheduling
Operating systems with priority-based scheduling use a max-heap (or min-heap, depending on convention) to manage the ready queue. The process with the highest priority is always at the root and is the next to receive CPU time. When a new process arrives or a process changes priority, the heap is updated in O(log n). This ensures O(1) access to the next process to run and O(log n) for all updates.
📊
K-th Largest or Smallest Element
To find the k-th largest element in a stream of data, maintain a min-heap of size k. For each new element, if it is larger than the root (the current k-th largest), replace the root and sift-down. After processing all elements, the root holds the k-th largest. This runs in O(n log k) time and O(k) space — far better than sorting all n elements at O(n log n). Widely used in database query optimisation and real-time analytics.
Interactive Learning
Heap Quest and Array vs Linked List
Heap Quest shows insert, delete, and heap sort with a simultaneous tree-and-array view — every sift-up and sift-down is animated. The Heap Array vs Linked List game demonstrates why the parent formula works in O(1) with arrays but degrades to O(n) with linked lists.