A heap is a complete binary tree stored as an array that satisfies the heap property — each node is greater than or equal to its children (max-heap) or less than or equal (min-heap) — providing O(1) access to the maximum (or minimum) and O(log n) insert and extract.
A heap is a tree stored as an array where every parent is larger than its children (max-heap) or smaller (min-heap) — so the largest (or smallest) element is always at index 0, retrievable in O(1).
Array representation
A binary heap stores a complete binary tree in an array — no pointers needed. For a node at index i (0-based): left child at 2i+1, right child at 2i+2, parent at ⌊(i-1)/2⌋. A complete binary tree with n nodes has ⌊n/2⌋ internal nodes and ⌈n/2⌉ leaves. This layout means the tree is always as compact as possible — no wasted space.
| Operation | Time | Space | Notes |
|---|---|---|---|
| Get maximum (max-heap) | O(1) | O(1) | Always at index 0 |
| Insert | O(log n) | O(1) | Sift up from leaf |
| Extract max | O(log n) | O(1) | Remove root, sift down |
| Build from array | O(n) | O(1) | Bottom-up heapify |
| Decrease key | O(log n) | O(1) | Sift up after change |
| Delete arbitrary | O(log n) | O(1) | Decrease to -∞, then extract |
import heapq # Python provides a min-heap
# Build heap from a list — O(n)
nums = [5, 2, 8, 1, 9, 3, 7]
heapq.heapify(nums)
print(nums[0]) # 1 — minimum always at index 0
# Insert — O(log n)
heapq.heappush(nums, 0)
print(nums[0]) # 0 — new minimum
# Extract minimum — O(log n)
print(heapq.heappop(nums)) # 0
print(heapq.heappop(nums)) # 1
# Peek without removing — O(1)
print(nums[0]) # 2Applications
A heap is the standard implementation of a priority queue — a data structure where the highest-priority element is always retrieved next. Applications: Dijkstra's shortest path algorithm (O((V+E) log V) with a heap vs. O(V²) without), A* search, Huffman encoding, job scheduling with priorities, finding the k largest elements in a stream.
Sift-up and sift-down
Sift-up (bubble-up): after inserting a new element at the end of the heap, compare it with its parent; if it violates the heap property, swap and continue upward. Stops when the heap property holds or the root is reached. Cost: O(height) = O(log n).
Sift-down (heapify): after replacing the root with the last element (extract-max), compare the new root with its children; swap with the larger child if it violates the heap property; continue downward. Cost: O(height) = O(log n).
class MaxHeap:
def __init__(self): self.data = []
def push(self, val):
self.data.append(val)
self._sift_up(len(self.data) - 1)
def pop(self):
if len(self.data) == 1: return self.data.pop()
top = self.data[0]
self.data[0] = self.data.pop() # move last to root
self._sift_down(0)
return top
def _sift_up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.data[i] > self.data[parent]:
self.data[i], self.data[parent] = self.data[parent], self.data[i]
i = parent
else: break
def _sift_down(self, i):
n = len(self.data)
while True:
largest, l, r = i, 2*i+1, 2*i+2
if l < n and self.data[l] > self.data[largest]: largest = l
if r < n and self.data[r] > self.data[largest]: largest = r
if largest == i: break
self.data[i], self.data[largest] = self.data[largest], self.data[i]
i = largestk-largest elements efficiently
Finding the k largest elements from n items: use a min-heap of size k. For each new element: if it is larger than the heap minimum, pop the minimum and push the new element. At the end, the heap contains the k largest elements. Time: O(n log k). Space: O(k). Python's heapq.nlargest(k, iterable) does this in one call.
O(n) build-heap: the formal proof
Building a heap bottom-up runs in O(n), not O(n log n). Formal proof: the height of a node at level h from the bottom is h. There are at most ⌈n/2h+1⌉ nodes at height h. Each node's heapify costs O(h). Total work = ∑h=0⌊log n⌋ ⌈n/2h+1⌉ ⋅ O(h) ≤ n ∑h=0∞ h/2h = 2n = O(n). The series ∑ h/2h converges because the exponential denominator dominates.
Fibonacci heaps
A Fibonacci heap (Fredman & Tarjan, 1987) is a collection of heap-ordered trees with lazy merging. Amortised complexities: O(1) insert, O(1) find-min, O(log n) extract-min, O(1) decrease-key, O(1) merge. The O(1) amortised decrease-key enables Dijkstra's algorithm to run in O(V log V + E) rather than O((V+E) log V). Fibonacci heaps are theoretically important but rarely used in practice due to high constant factors and implementation complexity.
Cormen, T. H. et al. (2022). CLRS (4th ed.), Ch.6 — Heapsort and binary heaps; Ch.19 — Fibonacci heaps. Williams, J. W. J. (1964). "Algorithm 232: Heapsort." CACM 7(6). Python heapq: docs.python.org/3/library/heapq.html.