Heap Data Structure: Complete Guide with Code Examples

A heap is a complete binary tree stored as an array where every parent satisfies the heap property: either always ≤ its children (min-heap) or always ≥ its children (max-heap). Heaps power priority queues, heap sort, and graph algorithms like Dijkstra.

They appear in roughly 15–20 % of coding interviews at major tech companies, and understanding them unlocks a whole family of "top-K" and "Kth largest/smallest" problems.

Quick reference

What is a heap?

A heap is a complete binary tree (all levels full except possibly the last, filled left to right) that satisfies the heap property:

• Min-heap: every node ≤ both children → root is the minimum element.
• Max-heap: every node ≥ both children → root is the maximum element.

Min-heap example:
        1
       / \
      3   5
     / \ / \
    7  8 9  6

As array: [1, 3, 5, 7, 8, 9, 6]

Array representation

Because a heap is a complete binary tree, it maps perfectly to an array — no pointers needed.

For a node at index i (0-based):

This means heap operations manipulate the array directly by comparing indices — extremely cache-friendly.

Min-heap vs Max-heap

Core operations

Insert (sift up)

Add the new element at the end of the array, then bubble it up while it violates the heap property.

Insert 2 into min-heap [1, 3, 5, 7, 8]:
Step 1: append → [1, 3, 5, 7, 8, 2]
Step 2: 2 < parent(5) → swap → [1, 3, 2, 7, 8, 5]
Step 3: 2 > parent(1) → stop
Result: [1, 3, 2, 7, 8, 5]

Remove min/max (sift down)

Swap the root with the last element, remove the last element, then sink the new root down while it violates the heap property.

Pop min from [1, 3, 2, 7, 8, 5]:
Step 1: swap root with last → [5, 3, 2, 7, 8, 1], remove 1
Step 2: 5 > min(3,2)=2 → swap with 2 → [2, 3, 5, 7, 8]
Step 3: 5 has no children → stop
Result: [2, 3, 5, 7, 8], returned 1

Heapify (build heap in O(n))

Given an arbitrary array, build a heap in O(n) — faster than inserting one by one (O(n log n)).

Start from the last non-leaf node (n//2 - 1) down to 0, sifting down each.

Array: [5, 3, 8, 1, 2, 9, 4]
Last non-leaf: index 2 (value 8)

Sift down 8: children 9,4 → 9>8 → swap 8,9 → [5,3,9,1,2,8,4]
Sift down 3: children 1,2 → 1<3 → swap 3,1 → [5,1,9,3,2,8,4]
Sift down 5: children 1,9 → 1<5 → swap 5,1 → [1,5,9,3,2,8,4]
             5's children 3,2 → 2<5 → swap 5,2 → [1,2,9,3,5,8,4]
Min-heap: [1, 2, 9, 3, 5, 8, 4]

Implementation in 4 languages

Python

Python's heapq module is a min-heap. For a max-heap, negate values.

import heapq

# Min-heap
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
heapq.heappush(min_heap, 1)

print(heapq.heappop(min_heap))  # 1 (minimum)
print(min_heap[0])              # 2 (peek without pop)

# Build heap from list in O(n)
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(heapq.heappop(nums))  # 1

# Max-heap: negate values
max_heap = []
for x in [5, 2, 8, 1]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))  # 8 (maximum)

# Heap with tuples: (priority, value)
tasks = []
heapq.heappush(tasks, (3, "low priority"))
heapq.heappush(tasks, (1, "urgent"))
heapq.heappush(tasks, (2, "medium"))
print(heapq.heappop(tasks))  # (1, 'urgent')

JavaScript

JavaScript has no built-in heap — here is a minimal generic implementation.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  _parent(i) { return Math.floor((i - 1) / 2); }
  _left(i)   { return 2 * i + 1; }
  _right(i)  { return 2 * i + 2; }
  _swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

  push(val) {
    this.heap.push(val);
    this._siftUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._siftDown(0);
    return min;
  }

  peek() { return this.heap[0]; }
  size() { return this.heap.length; }

  _siftUp(i) {
    while (i > 0) {
      const p = this._parent(i);
      if (this.heap[p] > this.heap[i]) {
        this._swap(p, i);
        i = p;
      } else break;
    }
  }

  _siftDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = this._left(i), r = this._right(i);
      if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
      if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
      if (smallest === i) break;
      this._swap(i, smallest);
      i = smallest;
    }
  }
}

// Usage
const heap = new MinHeap();
heap.push(5); heap.push(2); heap.push(8); heap.push(1);
console.log(heap.pop()); // 1
console.log(heap.peek()); // 2

Java

import java.util.PriorityQueue;
import java.util.Collections;

public class HeapExample {
    public static void main(String[] args) {
        // Min-heap (default)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        System.out.println(minHeap.poll()); // 1
        System.out.println(minHeap.peek()); // 2

        // Max-heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);

        System.out.println(maxHeap.poll()); // 8

        // Custom comparator (e.g., by string length)
        PriorityQueue<String> byLength = new PriorityQueue<>(
            (a, b) -> a.length() - b.length()
        );
        byLength.offer("banana");
        byLength.offer("fig");
        byLength.offer("apple");
        System.out.println(byLength.poll()); // "fig"
    }
}

Go

package main

import (
    "container/heap"
    "fmt"
)

// IntMinHeap implements heap.Interface for a min-heap of ints
type IntMinHeap []int

func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntMinHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntMinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func main() {
    h := &IntMinHeap{5, 2, 8, 1}
    heap.Init(h)

    heap.Push(h, 3)
    fmt.Println(heap.Pop(h)) // 1
    fmt.Println((*h)[0])     // 2 (peek)
}

Heap sort

Heap sort runs in O(n log n) time and O(1) extra space (in-place). It is not stable.

Algorithm:

1. Build a max-heap from the array — O(n).
2. Repeatedly swap the root (max) with the last unsorted element and sift down — O(n log n).

def heap_sort(arr):
    n = len(arr)

    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        _sift_down_max(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # move current max to end
        _sift_down_max(arr, i, 0)          # restore heap on reduced array

def _sift_down_max(arr, n, i):
    while True:
        largest, l, r = i, 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

nums = [12, 11, 13, 5, 6, 7]
heap_sort(nums)
print(nums)  # [5, 6, 7, 11, 12, 13]

Heap sort vs other sorts

Heap sort is rarely used in practice because quicksort and Timsort have better cache performance, but it matters when you need guaranteed O(n log n) with O(1) space.

Priority queue

A priority queue is an abstract data type where each element has a priority and dequeue always returns the highest-priority element. Heaps are the most common implementation.

import heapq

# Event-driven simulation: (time, event)
events = []
heapq.heappush(events, (10, "task C"))
heapq.heappush(events, (1,  "task A"))
heapq.heappush(events, (5,  "task B"))

while events:
    time, task = heapq.heappop(events)
    print(f"t={time}: {task}")
# t=1: task A
# t=5: task B
# t=10: task C

Priority queue vs heap

Classic interview problems

1. Kth largest element (LeetCode 215)

Maintain a min-heap of size K. After scanning all elements, the root is the Kth largest.

import heapq

def kth_largest(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)         # O(k)

    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)  # O(log k)

    return min_heap[0]              # root = Kth largest

print(kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Time: O(n log k). Space: O(k). — Much better than sorting O(n log n).

2. Merge K sorted lists (LeetCode 23)

import heapq

def merge_k_sorted(lists):
    result = []
    heap = []

    # Push (value, list_index, element_index) for each list's first element
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, li, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(lists[li]):
            next_val = lists[li][ei + 1]
            heapq.heappush(heap, (next_val, li, ei + 1))

    return result

print(merge_k_sorted([[1,4,7],[2,5,8],[3,6,9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time: O(n log k) where n = total elements, k = number of lists.

3. Top K frequent elements (LeetCode 347)

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Use min-heap of size k; pop when exceeds k
    return heapq.nlargest(k, count.keys(), key=count.get)

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]

4. Find median from data stream (LeetCode 295)

Use two heaps: a max-heap for the lower half and a min-heap for the upper half.

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []   # max-heap (negated)
        self.upper = []   # min-heap

    def add_num(self, num):
        # Push to max-heap (lower half)
        heapq.heappush(self.lower, -num)

        # Balance: ensure lower's max <= upper's min
        if self.upper and -self.lower[0] > self.upper[0]:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))

        # Balance sizes: lower can have at most 1 more element
        if len(self.lower) > len(self.upper) + 1:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))
        elif len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def find_median(self):
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2.0

mf = MedianFinder()
for n in [1, 2, 3]:
    mf.add_num(n)
    print(mf.find_median())  # 1.0, 1.5, 2.0

5. K closest points to origin (LeetCode 973)

import heapq
import math

def k_closest(points, k):
    # Max-heap of size k (negate distance)
    heap = []
    for x, y in points:
        dist = x*x + y*y           # no need for sqrt when comparing
        heapq.heappush(heap, (-dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)    # remove farthest
    return [[x, y] for _, x, y in heap]

print(k_closest([[1,3],[-2,2],[5,8],[0,1]], 2))
# [[-2, 2], [0, 1]]

6. Dijkstra's shortest path

The heap is the core of Dijkstra — always process the unvisited node with the smallest tentative distance.

import heapq

def dijkstra(graph, start):
    """graph: {node: [(neighbor, weight), ...]}"""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]     # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue         # outdated entry
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

When to use a heap

When NOT to use a heap

Heap variants

In practice, the binary heap covers 99 % of use cases. Fibonacci heaps are theoretically superior but rarely implemented.

Complexity summary

Common mistakes

Heap vs related data structures

Frequently asked questions

Q: Is a heap the same as a priority queue?
A heap is one implementation of a priority queue. A priority queue is the abstract concept; a heap (usually binary heap) is how it is typically implemented.

Q: Why is building a heap O(n) and not O(n log n)?
Because most nodes are near the leaves and sift down very little. A rigorous analysis shows the total work is bounded by a geometric series summing to O(n). Inserting one by one uses O(n log n) because it calls sift-up on every element.

Q: Can you search a heap efficiently?
No. Heaps only guarantee the min/max at the root. A search requires O(n) scanning. Use a balanced BST or hash map if you need fast lookups.

Q: When should I use a min-heap vs max-heap for Kth largest problems?
Use a min-heap of size K. The root of the min-heap is always the Kth largest seen so far. If a new element is larger than the root, replace it. This keeps only the K largest elements.

Q: What is the difference between heapq.heappush + heapq.heappop and heapq.heapreplace?
heapreplace(heap, item) pops the smallest and pushes the new item in one O(log n) operation — more efficient than separate pop + push when you always want to maintain a fixed heap size.

Q: Are heaps used in real-world systems?
Yes — operating system schedulers, network routers (QoS), database query planners (merge joins), event-driven simulators, A* pathfinding in games, and streaming analytics (top-K counters).