Heap Data Structure from Scratch (2026)
A 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 Ayodhyyya. Last updated June 1, 2026.