ayodhyya.comA Heap is a complete binary tree that satisfies the heap property: in a max-heap, the parent is always greater than or equal to its children; in a min-heap, it is smaller than or equal to its children. Heaps are typically implemented using arrays where the root is at index 0, the left child at 2i+1, and the right child at 2i+2.
Heaps are the backbone of priority queues, used in algorithms like Dijkstra's shortest path, Prim's MST, Heap Sort, and task scheduling. The heapify operation runs in O(log n) and building a heap from an unsorted array takes O(n).
Insert and Extract Operations
Insertion adds the element at the end (next available position) and then bubbles it up (percolate up) by swapping with the parent until the heap property is restored. Extract removes the root, replaces it with the last element, and bubbles it down (heapify) by swapping with the larger (max-heap) or smaller (min-heap) child.
void insert(vector& heap, int val) {
heap.push_back(val);
int i = heap.size() - 1;
while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
swap(heap[(i - 1) / 2], heap[i]);
i = (i - 1) / 2;
}
}
int extractMax(vector& heap) {
int root = heap[0];
heap[0] = heap.back(); heap.pop_back();
heapify(heap, heap.size(), 0);
return root;
} Heap Sort
Heap Sort uses a max-heap to sort in ascending order. First, build a max-heap from the array (O(n)). Then repeatedly extract the maximum (swap root with last element, reduce heap size, and heapify the root). This produces a sorted array in-place in O(n log n).
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}Frequently Asked Questions
Why does building a heap take O(n) time?
The heapify operation on smaller nodes runs faster. Most nodes are near the bottom β there are n/2 nodes at the leaf level that don't need heapify. The sum of work across all levels converges to O(n).
Is a Heap the same as a Priority Queue?
A priority queue is an abstract data type (ADT). A heap is the most common concrete implementation of a priority queue, but other implementations (like Fibonacci heaps) also exist.
Originally published on Ayodhyya. Last updated June 1, 2026.
Array Representation
A binary heap is stored as an array where the children of index i are at 2i+1 and 2i+2, and the parent is at floor((i-1)/2). This compact representation needs no pointers and has excellent cache locality.
Heapify: Building in O(n)
Calling sift-down on every non-leaf node (from index n/2 down to 0) builds a heap in O(n) time, not O(n log n). The proof: most nodes are near the bottom and have small heights, so the total work is linear.
Priority Queues and Scheduling
Heaps power priority queues used in OS task schedulers, Dijkstra's shortest path, Huffman coding, and the Java PriorityQueue / C++ priority_queue containers. Insert and extract-min are both O(log n).
Heap Sort
Building a heap then repeatedly extracting the max gives an in-place O(n log n) sort. It is not stable and has poor cache performance compared to merge sort, but its O(1) space makes it useful in memory-constrained environments.
Array Representation
A binary heap is stored as an array where the children of index i are at 2i+1 and 2i+2, and the parent is at floor((i-1)/2). This compact representation needs no pointers and has excellent cache locality.<\/p>
Heapify: Building in O(n)
Calling sift-down on every non-leaf node (from index n/2 down to 0) builds a heap in O(n) time, not O(n log n). The proof: most nodes are near the bottom and have small heights, so the total work is linear.<\/p>
Priority Queues and Scheduling
Heaps power priority queues used in OS task schedulers, Dijkstra's shortest path, Huffman coding, and the Java PriorityQueue / C++ priority_queue containers. Insert and extract-min are both O(log n).<\/p>
Heap Sort
Building a heap then repeatedly extracting the max gives an in-place O(n log n) sort. It is not stable and has poor cache performance compared to merge sort, but its O(1) space makes it useful in memory-constrained environments.<\/p>