Heaps and Priority Queues

November 19, 2025

#heap #priority-queue #min-heap #max-heap #data-structures #algorithms #interviewing

Introduction

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, parent nodes are always greater than or equal to their children; in a min-heap, parent nodes are always less than or equal to their children. Heaps are the foundation for priority queues and enable efficient algorithms like heap sort and finding the kth largest element.

Unlike Binary Search Trees, heaps don’t maintain a fully sorted order—they only guarantee the min/max element is at the root. This relaxed ordering enables O(1) access to the min/max and O(log n) insertions and deletions.

Review Binary Trees, Arrays, and Big-O Notation first if needed.

Heaps provide O(1) access to the minimum (min-heap) or maximum (max-heap) element and O(log n) insertion and deletion, making them ideal for priority queues and algorithms requiring repeated min/max access.

What is a heap?

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

Min-Heap Property

Every parent node ≤ its children

Root (1) is the minimum element.

Max-Heap Property

Every parent node ≥ its children

Root (10) is the maximum element.

Why use a heap?

Choose a heap when:

You need repeated access to min/max element
You’re implementing a priority queue
You need heap sort (in-place, O(n log n))
You’re finding the kth largest/smallest element
You’re merging k sorted lists
You need efficient median tracking in a stream
You’re implementing Dijkstra’s shortest path algorithm

Avoid a heap when:

You need arbitrary access to elements (use array)
You need full sorting (use sorting algorithms or BST)
You need FIFO order (use queue)
You need O(1) lookup by key (use hash table)

Real-world applications

Heaps are used extensively:

Operating systems: CPU task scheduling (priority queues)
Dijkstra’s algorithm: Finding shortest paths in graphs
Event-driven simulation: Processing events by priority/time
Data compression: Huffman coding uses min-heaps
Load balancing: Distributing tasks by priority
A pathfinding*: Managing open set in game AI
K-way merge: Merging multiple sorted streams
Real-time systems: Managing tasks by deadline

Heap representation

Heaps are typically implemented using arrays (not pointers) for efficiency:

Array: [10, 7, 9, 3, 5, 4, 8]
Index:  0  1  2  3  4  5  6

Visualized as tree:
      10
      / \
     7   9
    / \ / \
   3  5 4  8

Array indexing formulas (0-indexed):

Parent of node at index i: (i - 1) / 2
Left child of node at index i: 2 * i + 1
Right child of node at index i: 2 * i + 2

Alternative (1-indexed):

Parent: i / 2
Left child: 2 * i
Right child: 2 * i + 1

Heap operations

Heapify (Bubble Down)

After removing the root or violating the heap property, restore it by moving elements down.

Bubble Up

After insertion, restore heap property by moving the element up.

Min-Heap implementation

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

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // Insert element (O(log n))
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[index] >= this.heap[parentIndex]) break;

      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  // Extract minimum (O(log n))
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  heapifyDown(index) {
    while (true) {
      let smallest = index;
      const left = this.getLeftChildIndex(index);
      const right = this.getRightChildIndex(index);

      if (left < this.heap.length &&
          this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      if (right < this.heap.length &&
          this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest === index) break;

      this.swap(index, smallest);
      index = smallest;
    }
  }

  // Peek at minimum (O(1))
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

// Example usage
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);

console.log(minHeap.peek());         // 1
console.log(minHeap.extractMin());   // 1
console.log(minHeap.extractMin());   // 3
console.log(minHeap.peek());         // 5

class MinHeap:
    def __init__(self):
        self.heap = []

    def get_parent_index(self, i):
        return (i - 1) // 2

    def get_left_child_index(self, i):
        return 2 * i + 1

    def get_right_child_index(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 element (O(log n))"""
        self.heap.append(value)
        self.bubble_up(len(self.heap) - 1)

    def bubble_up(self, index):
        while index > 0:
            parent_index = self.get_parent_index(index)
            if self.heap[index] >= self.heap[parent_index]:
                break

            self.swap(index, parent_index)
            index = parent_index

    def extract_min(self):
        """Extract minimum (O(log n))"""
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return min_val

    def heapify_down(self, index):
        while True:
            smallest = index
            left = self.get_left_child_index(index)
            right = self.get_right_child_index(index)

            if (left < len(self.heap) and
                self.heap[left] < self.heap[smallest]):
                smallest = left

            if (right < len(self.heap) and
                self.heap[right] < self.heap[smallest]):
                smallest = right

            if smallest == index:
                break

            self.swap(index, smallest)
            index = smallest

    def peek(self):
        """Peek at minimum (O(1))"""
        return self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)

    def is_empty(self):
        return len(self.heap) == 0

# Example usage
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
min_heap.insert(1)

print(min_heap.peek())          # 1
print(min_heap.extract_min())   # 1
print(min_heap.extract_min())   # 3
print(min_heap.peek())          # 5

import java.util.ArrayList;
import java.util.List;

public class MinHeap {
    private List<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }

    private int getParentIndex(int i) {
        return (i - 1) / 2;
    }

    private int getLeftChildIndex(int i) {
        return 2 * i + 1;
    }

    private int getRightChildIndex(int i) {
        return 2 * i + 2;
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    // Insert element (O(log n))
    public void insert(int value) {
        heap.add(value);
        bubbleUp(heap.size() - 1);
    }

    private void bubbleUp(int index) {
        while (index > 0) {
            int parentIndex = getParentIndex(index);
            if (heap.get(index) >= heap.get(parentIndex)) break;

            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    // Extract minimum (O(log n))
    public Integer extractMin() {
        if (heap.isEmpty()) return null;
        if (heap.size() == 1) return heap.remove(0);

        int min = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1));
        heapifyDown(0);
        return min;
    }

    private void heapifyDown(int index) {
        while (true) {
            int smallest = index;
            int left = getLeftChildIndex(index);
            int right = getRightChildIndex(index);

            if (left < heap.size() &&
                heap.get(left) < heap.get(smallest)) {
                smallest = left;
            }

            if (right < heap.size() &&
                heap.get(right) < heap.get(smallest)) {
                smallest = right;
            }

            if (smallest == index) break;

            swap(index, smallest);
            index = smallest;
        }
    }

    // Peek at minimum (O(1))
    public Integer peek() {
        return heap.isEmpty() ? null : heap.get(0);
    }

    public int size() {
        return heap.size();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.insert(10);
        minHeap.insert(5);
        minHeap.insert(3);
        minHeap.insert(8);
        minHeap.insert(1);

        System.out.println(minHeap.peek());         // 1
        System.out.println(minHeap.extractMin());   // 1
        System.out.println(minHeap.extractMin());   // 3
        System.out.println(minHeap.peek());         // 5
    }
}

Building a heap from an array

Instead of inserting elements one by one (O(n log n)), we can build a heap in O(n) using heapify:

class MinHeap {
  // ... previous code

  buildHeap(array) {
    this.heap = [...array];
    // Start from last non-leaf node and heapify down
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }
}

const heap = new MinHeap();
heap.buildHeap([9, 5, 6, 2, 3, 7, 1, 4, 8]);
console.log(heap.heap);  // [1, 2, 6, 4, 3, 7, 9, 5, 8] (valid min-heap)

class MinHeap:
    # ... previous code

    def build_heap(self, array):
        self.heap = array.copy()
        # Start from last non-leaf node and heapify down
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self.heapify_down(i)

heap = MinHeap()
heap.build_heap([9, 5, 6, 2, 3, 7, 1, 4, 8])
print(heap.heap)  # [1, 2, 6, 4, 3, 7, 9, 5, 8] (valid min-heap)

public void buildHeap(int[] array) {
    heap = new ArrayList<>();
    for (int val : array) {
        heap.add(val);
    }
    // Start from last non-leaf node and heapify down
    for (int i = heap.size() / 2 - 1; i >= 0; i--) {
        heapifyDown(i);
    }
}

int[] arr = {9, 5, 6, 2, 3, 7, 1, 4, 8};
heap.buildHeap(arr);
System.out.println(heap.heap);  // [1, 2, 6, 4, 3, 7, 9, 5, 8]

Heap sort

Use a heap to sort an array in O(n log n) time:

function heapSort(array) {
  const heap = new MinHeap();
  heap.buildHeap(array);

  const sorted = [];
  while (!heap.isEmpty()) {
    sorted.push(heap.extractMin());
  }

  return sorted;
}

console.log(heapSort([9, 5, 6, 2, 3, 7, 1, 4, 8]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

def heap_sort(array):
    heap = MinHeap()
    heap.build_heap(array)

    sorted_arr = []
    while not heap.is_empty():
        sorted_arr.append(heap.extract_min())

    return sorted_arr

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

public static int[] heapSort(int[] array) {
    MinHeap heap = new MinHeap();
    heap.buildHeap(array);

    int[] sorted = new int[array.length];
    int i = 0;
    while (!heap.isEmpty()) {
        sorted[i++] = heap.extractMin();
    }

    return sorted;
}

int[] arr = {9, 5, 6, 2, 3, 7, 1, 4, 8};
System.out.println(Arrays.toString(heapSort(arr)));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

Common heap problems

Find kth largest element

function findKthLargest(nums, k) {
  const minHeap = new MinHeap();

  for (const num of nums) {
    minHeap.insert(num);
    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }

  return minHeap.peek();
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));  // 5

def find_kth_largest(nums, k):
    min_heap = MinHeap()

    for num in nums:
        min_heap.insert(num)
        if min_heap.size() > k:
            min_heap.extract_min()

    return min_heap.peek()

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

public static int findKthLargest(int[] nums, int k) {
    MinHeap minHeap = new MinHeap();

    for (int num : nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.extractMin();
        }
    }

    return minHeap.peek();
}

System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
// 5

Merge k sorted lists

function mergeKSortedLists(lists) {
  const minHeap = new MinHeap();
  const result = [];

  // Insert first element from each list with index tracking
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) {
      minHeap.insert({value: lists[i][0], listIdx: i, elemIdx: 0});
    }
  }

  while (!minHeap.isEmpty()) {
    const {value, listIdx, elemIdx} = minHeap.extractMin();
    result.push(value);

    // Add next element from same list
    if (elemIdx + 1 < lists[listIdx].length) {
      minHeap.insert({
        value: lists[listIdx][elemIdx + 1],
        listIdx,
        elemIdx: elemIdx + 1
      });
    }
  }

  return result;
}

console.log(mergeKSortedLists([[1, 4, 5], [1, 3, 4], [2, 6]]));
// [1, 1, 2, 3, 4, 4, 5, 6]

import heapq

def merge_k_sorted_lists(lists):
    # Python has built-in heapq module
    heap = []
    result = []

    # Insert first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        value, list_idx, elem_idx = heapq.heappop(heap)
        result.append(value)

        # Add next element from same list
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (
                lists[list_idx][elem_idx + 1],
                list_idx,
                elem_idx + 1
            ))

    return result

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

import java.util.PriorityQueue;

public static List<Integer> mergeKSortedLists(int[][] lists) {
    // Java has built-in PriorityQueue (min-heap)
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(
        (a, b) -> a[0] - b[0]  // Compare by value
    );
    List<Integer> result = new ArrayList<>();

    // Insert first element from each list
    for (int i = 0; i < lists.length; i++) {
        if (lists[i].length > 0) {
            minHeap.offer(new int[]{lists[i][0], i, 0});
        }
    }

    while (!minHeap.isEmpty()) {
        int[] curr = minHeap.poll();
        int value = curr[0], listIdx = curr[1], elemIdx = curr[2];
        result.add(value);

        // Add next element from same list
        if (elemIdx + 1 < lists[listIdx].length) {
            minHeap.offer(new int[]{
                lists[listIdx][elemIdx + 1],
                listIdx,
                elemIdx + 1
            });
        }
    }

    return result;
}

Complexity analysis

Operation	Time Complexity	Space Complexity
Insert	O(log n)	O(1)
Extract Min/Max	O(log n)	O(1)
Peek Min/Max	O(1)	O(1)
Build Heap	O(n)	O(n)
Heap Sort	O(n log n)	O(1) in-place
Delete arbitrary	O(log n)	O(1)
Search	O(n)	O(1)

Common pitfalls

Not maintaining complete tree: Heaps must be complete binary trees
Confusing min-heap and max-heap: Know which you need
Off-by-one errors: Array indexing formulas are tricky
Not heapifying after changes: Always restore heap property after modifications
Using heap for searching: Heaps are not for general searching (O(n))

When to prefer other data structures

Need full sorting → Use sorting algorithms
Need O(1) arbitrary access → Use array
Need O(1) key lookup → Use hash table
Need ordered traversal → Use BST
Need FIFO → Use queue

Practice problems

Find the kth smallest element in an array
Find median from data stream
Merge k sorted arrays
Top K frequent elements
Find K closest points to origin
Task scheduler with cooldown periods
Ugly number II (numbers with only 2, 3, 5 as prime factors)
Sort a nearly sorted (k-sorted) array
Maximum sum of distinct subarrays with length k
Sliding window maximum using heap
Reorganize string so no two adjacent characters are same
Design Twitter feed (combine k user timelines)
Trapping rain water using heaps
Smallest range covering elements from k lists
Find the most competitive subsequence

Complexity summary

Time:
- Insert/Delete: O(log n)
- Peek: O(1)
- Build heap: O(n)
- Heap sort: O(n log n)
Space: O(n) for storing n elements

Heaps provide the perfect balance between fully sorted structures (BSTs) and unsorted structures, offering efficient access to the min/max element while maintaining dynamic insertion and deletion.

Table of Contents