Heap / Priority Queue

Efficiently track the k-th largest/smallest element or merge sorted sequences.

9 problems 0 Easy 7 Medium 2 Hard

Overview

A heap provides O(log n) insertion and O(1) access to the min or max element. It shines in streaming data problems and k-th element queries.

When to Use

Kth largest/smallest element
Merge k sorted lists
Task scheduler
Find median from data stream
Top k frequent elements
Dijkstra's algorithm

Common Mistakes

Using a max-heap when a min-heap is needed (or vice versa)
Not updating heap when element changes (use lazy deletion)
Heap sort is O(n log n) but worse constants than quicksort

Complexity

Time

O(log n) insert/delete, O(1) peek

Space

O(n)

// Min-heap simulation in JS using sorted array (use a real heap in interviews)
class MinHeap {
  constructor() { this.heap = []; }
  push(val) {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b); // simplified
  }
  pop() { return this.heap.shift(); }
  peek() { return this.heap[0]; }
  size() { return this.heap.length; }
}

Problems (9)

Hide completed

Problem	Difficulty	Companies	Freq	Link
Kth Largest Element in an Array	Medium	FacebookAmazon +2	High
Find Median from Data Stream	Hard	AmazonMicrosoft +1	High
Task Scheduler	Medium	FacebookAmazon	Medium
Merge K Sorted Lists	Hard	AmazonFacebook +2	High
K Closest Points to Origin	Medium	FacebookAmazon +2	High
Reorganize String	Medium	AmazonGoogle +1	Medium
Top K Frequent Words	Medium	AmazonBloomberg +1	Medium
Find K Pairs with Smallest Sums	Medium	AmazonGoogle +1	Medium
Minimum Cost to Connect Sticks ★	Medium	AmazonFacebook	Medium	★

The heap is the secret weapon for top-K, K closest, and merge-K problems. Here's how it works and th…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee