Heap (Binary Heap)
Last updated
A binary heap is a complete binary tree that keeps the smallest (min-heap) or largest (max-heap) value at the root. This visualization is a min-heap: every parent is less than or equal to its children. To add a value you append it at the next open slot, then "sift it up" - swapping it with its parent while it's smaller - until the heap property holds again. Press play above to watch each new value bubble up to its place.
Because a heap is a complete tree, it's stored compactly in an array: node i's children are at 2i+1 and 2i+2. Insert and remove-min are O(log n) (one path from root to leaf), while peeking at the min is O(1) - which is exactly what a priority queue needs.
Time & space complexity
| Operation | Complexity | Notes |
|---|---|---|
| Peek min/max | O(1) | It's always the root |
| Insert (push) | O(log n) | Sift up one path |
| Remove min/max | O(log n) | Sift down one path |
| Build heap | O(n) | Heapify all at once |
| Space | O(n) | Array-backed, no pointers |
Step by step (push)
| Step | What happens |
|---|---|
| 1 | Append the new value at the end (next open leaf). |
| 2 | Compare it with its parent. |
| 3 | If it's smaller (min-heap), swap it up. |
| 4 | Repeat until it's no longer smaller than its parent, or reaches the root. |
Worked example
Building a min-heap by pushing [5, 3, 8, 1, 4] one value at a time:
| Push | Array after sift-up | Action |
|---|---|---|
5 | [5] | First value becomes the root. |
3 | [3, 5] | 3 < parent 5, so swap it up to the root. |
8 | [3, 5, 8] | 8 > parent 5, so it stays as a leaf. |
1 | [1, 3, 8, 5] | 1 < parent 5, swap; then 1 < parent 3, swap to the root. |
4 | [1, 3, 8, 5, 4] | 4 > parent 3, so it stays; the min 1 remains at the root. |
When to use a heap
| Use it when | Avoid it when |
|---|---|
| You repeatedly need the smallest or largest item from a changing set. | You need to search for arbitrary values, not just the extreme - use a BST or hash set. |
| You're implementing a priority queue for Dijkstra, A*, or a scheduler. | You need the data kept in fully sorted order at all times. |
You want O(log n) insert and remove-min with a compact array layout. | You need fast lookup or removal of a specific (non-root) element. |
| You need to merge a stream of items and pull them out by priority. | The dataset is tiny and a linear scan is simpler and fast enough. |
Heap (Priority Queue) code
A clean, runnable Heap (Priority Queue) implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Heap (Priority Queue) code in Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Heap (Priority Queue) code in JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Heap (Priority Queue) code in Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Heap (Priority Queue) code in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Heap (Priority Queue) code in C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Heap FAQ
What is a heap used for?
Heaps implement priority queues, which power Dijkstra's shortest-path algorithm, task schedulers, and event simulations. They're also the engine behind heapsort. Any time you repeatedly need the smallest or largest item from a changing set, a heap is the tool.
What is the difference between a heap and a binary search tree?
Both are binary trees, but a BST keeps a full left-to-right sorted order (enabling ordered search), while a heap only guarantees the parent-child relationship (min or max at the root). A heap gives O(1) access to the extreme value; a BST gives O(log n) search for any value.
Why is a heap stored in an array?
Because a heap is always a complete binary tree, its nodes map perfectly onto array indices: the children of index
i are at 2i+1 and 2i+2, and the parent is at (i-1)/2. This avoids storing child pointers and gives excellent cache performance.Is a heap the same as a sorted array?
No. A heap only guarantees that each parent is smaller (min-heap) or larger (max-heap) than its children, so siblings and cousins are in no particular order. A sorted array is fully ordered but costs
O(n) to insert into, whereas a heap inserts in O(log n) while still giving instant access to the extreme value.When should I use a heap instead of just sorting an array?
Reach for a heap when the data keeps changing and you only ever need the current minimum or maximum - inserting and popping cost
O(log n) each, versus re-sorting the whole array. If you have a static dataset and want every element in order, a single O(n log n) sort is simpler and often faster.Does building a heap from n items take O(n log n)?
Not if you build it all at once. Inserting
n items one by one is O(n log n), but the bottom-up heapify that sifts down from the last parent to the root runs in O(n) overall, because most nodes are near the bottom and sift down only a short distance.Related resources
More visualizations
