Heaps and Priority Queues - Complete Guide

Heaps are tree-based data structures that maintain a specific ordering property. This guide covers heap operations, priority queues, and common heap problems.

What is a Heap? #

A heap is a complete binary tree where each node satisfies the heap property:

  • Max Heap: Parent ≥ children
  • Min Heap: Parent ≤ children
Max Heap:          Min Heap:
     50                 10
    /  \               /  \
   30   40            20   30
  / \   /            / \   /
 10 20 35           40 50 35

Array Representation #

Heaps are typically stored in arrays.

// Array: [50, 30, 40, 10, 20, 35]
// Indices: 0   1   2   3   4   5

// For node at index i:
// Left child:  2 * i + 1
// Right child: 2 * i + 2
// Parent:      Math.floor((i - 1) / 2)

function leftChild(i) {
  return 2 * i + 1;
}

function rightChild(i) {
  return 2 * i + 2;
}

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

Min Heap Implementation #

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

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

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

  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex] <= this.heap[index]) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] =
        [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

  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.bubbleDown(0);

    return min;
  }

  bubbleDown(index) {
    while (true) {
      const leftIdx = 2 * index + 1;
      const rightIdx = 2 * index + 2;
      let smallest = index;

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

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

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }

  remove(value) {
    const index = this.heap.indexOf(value);
    if (index === -1) return false;

    if (index === this.heap.length - 1) {
      this.heap.pop();
      return true;
    }

    this.heap[index] = this.heap.pop();
    this.bubbleDown(index);
    this.bubbleUp(index);

    return true;
  }
}

// Usage
const heap = new MinHeap();
heap.insert(5);
heap.insert(3);
heap.insert(7);
heap.insert(1);

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

Max Heap Implementation #

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

  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex] >= this.heap[index]) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] =
        [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);

    return max;
  }

  bubbleDown(index) {
    while (true) {
      const leftIdx = 2 * index + 1;
      const rightIdx = 2 * index + 2;
      let largest = index;

      if (leftIdx < this.heap.length &&
          this.heap[leftIdx] > this.heap[largest]) {
        largest = leftIdx;
      }

      if (rightIdx < this.heap.length &&
          this.heap[rightIdx] > this.heap[largest]) {
        largest = rightIdx;
      }

      if (largest === index) break;

      [this.heap[index], this.heap[largest]] =
        [this.heap[largest], this.heap[index]];

      index = largest;
    }
  }
}

Priority Queue #

Priority queue using heap.

class PriorityQueue {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

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

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

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

  enqueue(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    if (this.size() === 1) return this.heap.pop();

    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);

    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.comparator(this.heap[parentIndex], this.heap[index]) <= 0) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] =
        [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

  bubbleDown(index) {
    while (true) {
      const leftIdx = 2 * index + 1;
      const rightIdx = 2 * index + 2;
      let smallest = index;

      if (leftIdx < this.heap.length &&
          this.comparator(this.heap[leftIdx], this.heap[smallest]) < 0) {
        smallest = leftIdx;
      }

      if (rightIdx < this.heap.length &&
          this.comparator(this.heap[rightIdx], this.heap[smallest]) < 0) {
        smallest = rightIdx;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }
}

// Usage with objects
const pq = new PriorityQueue((a, b) => a.priority - b.priority);

pq.enqueue({ task: 'Low priority', priority: 3 });
pq.enqueue({ task: 'High priority', priority: 1 });
pq.enqueue({ task: 'Medium priority', priority: 2 });

console.log(pq.dequeue());  // { task: 'High priority', priority: 1 }
console.log(pq.dequeue());  // { task: 'Medium priority', priority: 2 }

Heapify #

Convert array to heap in O(n).

function heapify(arr) {
  // Start from last non-leaf node
  const start = Math.floor(arr.length / 2) - 1;

  for (let i = start; i >= 0; i--) {
    bubbleDown(arr, i);
  }

  return arr;
}

function bubbleDown(arr, index) {
  const length = arr.length;

  while (true) {
    const leftIdx = 2 * index + 1;
    const rightIdx = 2 * index + 2;
    let largest = index;

    if (leftIdx < length && arr[leftIdx] > arr[largest]) {
      largest = leftIdx;
    }

    if (rightIdx < length && arr[rightIdx] > arr[largest]) {
      largest = rightIdx;
    }

    if (largest === index) break;

    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    index = largest;
  }
}

const arr = [3, 9, 2, 1, 4, 5];
heapify(arr);
console.log(arr);  // [9, 4, 5, 1, 3, 2] (max heap)

Heap Sort #

function heapSort(arr) {
  // Build max heap
  heapify(arr);

  // Extract elements
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    bubbleDownWithSize(arr, 0, i);
  }

  return arr;
}

function bubbleDownWithSize(arr, index, size) {
  while (true) {
    const leftIdx = 2 * index + 1;
    const rightIdx = 2 * index + 2;
    let largest = index;

    if (leftIdx < size && arr[leftIdx] > arr[largest]) {
      largest = leftIdx;
    }

    if (rightIdx < size && arr[rightIdx] > arr[largest]) {
      largest = rightIdx;
    }

    if (largest === index) break;

    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    index = largest;
  }
}

const arr = [3, 9, 2, 1, 4, 5];
heapSort(arr);
console.log(arr);  // [1, 2, 3, 4, 5, 9]

Classic Problems #

K Largest Elements #

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

  for (const num of nums) {
    minHeap.insert(num);

    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }

  return minHeap.heap;
}

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

K Smallest Elements #

function findKSmallest(nums, k) {
  const maxHeap = new MaxHeap();

  for (const num of nums) {
    maxHeap.insert(num);

    if (maxHeap.heap.length > k) {
      maxHeap.extractMax();
    }
  }

  return maxHeap.heap;
}

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

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

Top K Frequent Elements #

function topKFrequent(nums, k) {
  const freq = new Map();

  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }

  const minHeap = new PriorityQueue((a, b) => a[1] - b[1]);

  for (const [num, count] of freq) {
    minHeap.enqueue([num, count]);

    if (minHeap.size() > k) {
      minHeap.dequeue();
    }
  }

  return minHeap.heap.map(x => x[0]);
}

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));  // [1, 2]

Merge K Sorted Lists #

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

function mergeKLists(lists) {
  const pq = new PriorityQueue((a, b) => a.val - b.val);

  // Add first node from each list
  for (const list of lists) {
    if (list) {
      pq.enqueue(list);
    }
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (!pq.isEmpty()) {
    const node = pq.dequeue();
    current.next = node;
    current = current.next;

    if (node.next) {
      pq.enqueue(node.next);
    }
  }

  return dummy.next;
}

Find Median from Data Stream #

class MedianFinder {
  constructor() {
    this.maxHeap = new MaxHeap();  // Lower half
    this.minHeap = new MinHeap();  // Upper half
  }

  addNum(num) {
    // Add to max heap first
    this.maxHeap.insert(num);

    // Balance: max of lower half ≤ min of upper half
    this.minHeap.insert(this.maxHeap.extractMax());

    // Balance sizes
    if (this.minHeap.size() > this.maxHeap.heap.length) {
      this.maxHeap.insert(this.minHeap.extractMin());
    }
  }

  findMedian() {
    if (this.maxHeap.heap.length > this.minHeap.size()) {
      return this.maxHeap.heap[0];
    }

    return (this.maxHeap.heap[0] + this.minHeap.heap[0]) / 2;
  }
}

const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian());  // 1.5
mf.addNum(3);
console.log(mf.findMedian());  // 2

Kth Smallest Element in Matrix #

function kthSmallest(matrix, k) {
  const n = matrix.length;
  const pq = new PriorityQueue((a, b) => a.val - b.val);

  // Add first column
  for (let i = 0; i < Math.min(n, k); i++) {
    pq.enqueue({ val: matrix[i][0], row: i, col: 0 });
  }

  let result;

  for (let i = 0; i < k; i++) {
    const { val, row, col } = pq.dequeue();
    result = val;

    if (col + 1 < n) {
      pq.enqueue({ val: matrix[row][col + 1], row, col: col + 1 });
    }
  }

  return result;
}

const matrix = [
  [1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
];
console.log(kthSmallest(matrix, 8));  // 13

Meeting Rooms II #

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;

  intervals.sort((a, b) => a[0] - b[0]);

  const minHeap = new MinHeap();
  minHeap.insert(intervals[0][1]);

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= minHeap.peek()) {
      minHeap.extractMin();
    }

    minHeap.insert(intervals[i][1]);
  }

  return minHeap.size();
}

console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]]));  // 2

Task Scheduler #

function leastInterval(tasks, n) {
  const freq = new Map();

  for (const task of tasks) {
    freq.set(task, (freq.get(task) || 0) + 1);
  }

  const maxHeap = new MaxHeap();

  for (const count of freq.values()) {
    maxHeap.insert(count);
  }

  let time = 0;

  while (maxHeap.heap.length > 0) {
    const temp = [];

    for (let i = 0; i <= n; i++) {
      if (maxHeap.heap.length > 0) {
        temp.push(maxHeap.extractMax());
      }
    }

    for (const count of temp) {
      if (count - 1 > 0) {
        maxHeap.insert(count - 1);
      }
    }

    time += maxHeap.heap.length > 0 ? n + 1 : temp.length;
  }

  return time;
}

console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2));  // 8

Reorganize String #

function reorganizeString(s) {
  const freq = new Map();

  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }

  const maxHeap = new PriorityQueue((a, b) => b.count - a.count);

  for (const [char, count] of freq) {
    maxHeap.enqueue({ char, count });
  }

  const result = [];
  let prev = null;

  while (!maxHeap.isEmpty() || prev) {
    if (prev && maxHeap.isEmpty()) {
      return '';  // Impossible
    }

    const current = maxHeap.dequeue();
    result.push(current.char);
    current.count--;

    if (prev) {
      maxHeap.enqueue(prev);
      prev = null;
    }

    if (current.count > 0) {
      prev = current;
    }
  }

  return result.join('');
}

console.log(reorganizeString('aab'));   // 'aba'
console.log(reorganizeString('aaab'));  // ''

Time Complexity #

OperationTime Complexity
InsertO(log n)
Extract Min/MaxO(log n)
PeekO(1)
Build HeapO(n)
Heap SortO(n log n)
RemoveO(log n)

Space Complexity #

  • Heap: O(n)
  • Priority Queue: O(n)

Best Practices #

  1. Use min/max heap appropriately - K largest → min heap
  2. Heapify for large datasets - O(n) vs O(n log n)
  3. Priority queue for scheduling - Task scheduling
  4. Two heaps for median - Split data
  5. Consider alternatives - Sometimes sorting is simpler
  6. Custom comparators - For complex objects
  7. Balance heap sizes - For median finding

Heaps and priority queues are essential for solving ordering and scheduling problems efficiently. Master these data structures for interview success.

Previous Graph Algorithms - Complete Guide Tree Traversal Algorithms - Complete Guide Next