Heap
A heap is a specialized complete binary tree that satisfies the heap property. In a max-heap, every parent node is greater than or equal to its children, making the root the maximum element. Heaps are the backbone of priority queues and are used in algorithms like heap sort, Dijkstra's shortest path, and scheduling systems.
How it Works
A heap is a complete binary tree stored efficiently in an array. "Complete" means every level is fully filled except possibly the last, which is filled from left to right. This property guarantees the tree is balanced and allows a compact array representation with no wasted space.
Heap Property: In a max-heap, the value of each node is greater than or equal to the values of its children. This ensures the maximum element is always at the root (index 0). A min-heap is the reverse — each parent is less than or equal to its children, putting the minimum at the root.
Array Representation: Because the tree is complete, we can map nodes to array indices without any pointers:
- The root is at index
0. - For a node at index
i:- Left child is at index
2i + 1 - Right child is at index
2i + 2 - Parent is at index
floor((i - 1) / 2)
- Left child is at index
Key Operations:
- Insert: Add the new element at the end of the array (next available position in the tree), then bubble up (swap with parent) until the heap property is restored. Takes O(log n).
- Extract-Max: The root holds the maximum. Swap it with the last element, remove the last element, then sink down (swap with the larger child) until the heap property is restored. Takes O(log n).
- Heapify (Build Heap): Convert an arbitrary array into a valid max-heap by calling sink-down on every non-leaf node, starting from the last non-leaf and working up to the root. Despite appearances, this runs in O(n) time, not O(n log n).
Interactive Visualization
The tree view (top) shows the heap as a binary tree, while the array view (bottom) shows the same data in its underlying array form. Corresponding nodes and cells are highlighted together: red for active/swapping, yellow for parent being compared, and green for completed placement.
Code Implementation
Below are implementations of a max-heap with insert and extract_max operations. The array-based approach makes the code straightforward — parent and child indices are computed with simple arithmetic.
class MaxHeap:
def __init__(self):
self.heap = []
def _parent(self, i):
return (i - 1) // 2
def _left(self, i):
return 2 * i + 1
def _right(self, i):
return 2 * i + 2
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, value):
"""Insert a value and bubble up to restore heap property."""
self.heap.append(value)
idx = len(self.heap) - 1
# Bubble up
while idx > 0 and self.heap[idx] > self.heap[self._parent(idx)]:
self._swap(idx, self._parent(idx))
idx = self._parent(idx)
def extract_max(self):
"""Remove and return the maximum element (root)."""
if not self.heap:
raise IndexError("extract_max from empty heap")
max_val = self.heap[0]
last = self.heap.pop()
if self.heap:
self.heap[0] = last
self._sink_down(0)
return max_val
def _sink_down(self, idx):
"""Sink a node down to its correct position."""
n = len(self.heap)
while True:
largest = idx
left = self._left(idx)
right = self._right(idx)
if left < n and self.heap[left] > self.heap[largest]:
largest = left
if right < n and self.heap[right] > self.heap[largest]:
largest = right
if largest == idx:
break
self._swap(idx, largest)
idx = largest
def peek(self):
"""Return the maximum element without removing it."""
if not self.heap:
raise IndexError("peek from empty heap")
return self.heap[0]
# Example usage
h = MaxHeap()
for val in [40, 70, 30, 90, 50, 80, 60]:
h.insert(val)
print("Max:", h.peek()) # Output: Max: 90
print("Extracted:", h.extract_max()) # Output: Extracted: 90
print("New max:", h.peek()) # Output: New max: 80
import java.util.ArrayList;
import java.util.List;
public class MaxHeap {
private List<Integer> heap = new ArrayList<>();
private int parent(int i) { return (i - 1) / 2; }
private int left(int i) { return 2 * i + 1; }
private int right(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int tmp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, tmp);
}
/** Insert a value and bubble up to restore heap property. */
public void insert(int value) {
heap.add(value);
int idx = heap.size() - 1;
while (idx > 0 && heap.get(idx) > heap.get(parent(idx))) {
swap(idx, parent(idx));
idx = parent(idx);
}
}
/** Remove and return the maximum element (root). */
public int extractMax() {
if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
int maxVal = heap.get(0);
int last = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, last);
sinkDown(0);
}
return maxVal;
}
/** Sink a node down to its correct position. */
private void sinkDown(int idx) {
int n = heap.size();
while (true) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < n && heap.get(l) > heap.get(largest)) largest = l;
if (r < n && heap.get(r) > heap.get(largest)) largest = r;
if (largest == idx) break;
swap(idx, largest);
idx = largest;
}
}
/** Return the maximum element without removing it. */
public int peek() {
if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
return heap.get(0);
}
public static void main(String[] args) {
MaxHeap h = new MaxHeap();
int[] values = {40, 70, 30, 90, 50, 80, 60};
for (int v : values) h.insert(v);
System.out.println("Max: " + h.peek()); // 90
System.out.println("Extracted: " + h.extractMax()); // 90
System.out.println("New max: " + h.peek()); // 80
}
}
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
class MaxHeap {
vector<int> heap;
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }
void swap(int i, int j) { std::swap(heap[i], heap[j]); }
/** Sink a node down to its correct position. */
void sinkDown(int idx) {
int n = heap.size();
while (true) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < n && heap[l] > heap[largest]) largest = l;
if (r < n && heap[r] > heap[largest]) largest = r;
if (largest == idx) break;
swap(idx, largest);
idx = largest;
}
}
public:
/** Insert a value and bubble up to restore heap property. */
void insert(int value) {
heap.push_back(value);
int idx = heap.size() - 1;
while (idx > 0 && heap[idx] > heap[parent(idx)]) {
swap(idx, parent(idx));
idx = parent(idx);
}
}
/** Remove and return the maximum element (root). */
int extractMax() {
if (heap.empty()) throw runtime_error("Heap is empty");
int maxVal = heap[0];
heap[0] = heap.back();
heap.pop_back();
if (!heap.empty()) sinkDown(0);
return maxVal;
}
/** Return the maximum element without removing it. */
int peek() const {
if (heap.empty()) throw runtime_error("Heap is empty");
return heap[0];
}
};
int main() {
MaxHeap h;
int values[] = {40, 70, 30, 90, 50, 80, 60};
for (int v : values) h.insert(v);
cout << "Max: " << h.peek() << endl; // 90
cout << "Extracted: " << h.extractMax() << endl; // 90
cout << "New max: " << h.peek() << endl; // 80
return 0;
}
Complexity Analysis
Since a heap is a complete binary tree, its height is always O(log n). Both insert and extract operations traverse at most one root-to-leaf path, bounding their cost. The build-heap operation achieves O(n) through a clever bottom-up approach where most nodes are near the leaves and require very few swaps.
| Operation | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Insert | O(log n) | O(n) | Add element at the end, bubble up at most log n levels |
| Extract-Max | O(log n) | O(n) | Swap root with last, sink down at most log n levels |
| Peek | O(1) | O(n) | Maximum is always at index 0 (the root) |
| Build Heap | O(n) | O(n) | Bottom-up heapify; sum of sift-down costs converges to O(n) |
| Space | — | O(n) | Array of n elements; no additional pointer overhead |
Heaps are especially efficient as priority queues: they support insert and delete-max (or delete-min) in O(log n) time, with O(1) access to the extremal element. This makes them ideal for task schedulers, event-driven simulations, and graph algorithms like Dijkstra and Prim.
Quiz
Test your understanding of heaps with these questions.
Q1. In a max-heap stored as an array, which element is guaranteed to be the largest?
Q2. For a node at index i in a zero-indexed heap array, where is its left child?
i is at 2i + 1, and the right child is at 2i + 2. The formula 2i is used when the array is 1-indexed (starting from index 1).Q3. What is the time complexity of building a max-heap from an unsorted array of n elements?
Q4. After inserting a new element into a max-heap, which operation restores the heap property?
Q5. A max-heap has the array representation [100, 80, 90, 40, 50, 60, 30]. After extracting the maximum, what will the root be?