Learn › DSA Patterns

Pattern #3 · Heap · O(N log K)

Top K
Elements

Learn how a Min-Heap lets you find the largest K values in O(N log K) — without sorting the entire array.

🏆 Top K largest / smallest 📊 Kth largest / smallest 🔥 K most frequent elements

Scroll to learn

Story Time

The Treasure Hunt Leaderboard 🏴‍☠️

Before writing a single line of code, let's understand the intuition through a story.

👑

The King's Challenge

In a kingdom where treasure hunts were the grandest events, the king announced: "Find the Top 3 treasure hunters in the land!" Hundreds of adventurers rushed to collect gold coins — but scores kept arriving every second.

🧙

Heapster's Dilemma

The record keeper, a wise wizard named Heapster, faced a problem. "I can't sort thousands of scores every time a new one arrives — that's O(N log N) every update!" His apprentice suggested sorting… but scores kept pouring in.

🪄

The Magic Cauldron (Min-Heap!)

Heapster had an idea — a magical floating cauldron that holds exactly 3 scores. The cauldron's magic rule: the weakest score always floats to the top. When a new score arrives, compare it to the weakest in the cauldron:

✗ New score ≤ weakest? Ignore it.
✓ New score > weakest? Kick weakest out, add new score!

⬆️

A New Hunter Joins — HeapifyUp

John arrives with score 30. The cauldron has [45, 50, 70]. 30 < 45 (the top/min), so normally we'd ignore it — but watch what happens when we must add it:

Before

50 70

→

Add 30 at bottom

50 70

→

Bubble up!

45 70

⬇️

Root Removed — HeapifyDown

The weakest hunter (30) leaves. We move the last element (50) to the root, then sink it down until the heap property is restored:

Remove root (30)

45 70

→

50 → root, sink down

45 70

→

✓ Heap restored

50 70

🚀

Moral of the story

Heapster only ever tracks K scores at once. Every new score costs O(log K) — not O(N log N) for a full sort. The right data structure makes problems faster to solve!

Interactive

Heap Visualizer

Watch heapifyUp and heapifyDown step-by-step.

Initial heap: [45, 50, 70, 60, 90] — 45 is the minimum (root).

⌊(i−1) / 2⌋ Parent of node i

2i + 1 Left child of node i

2i + 2 Right child of node i

Complexity

Three Approaches

Approach	Time	Space	Best for
Sorting	O(N log N)	O(1)	Small arrays, simple code
Min-Heap Preferred ✓	O(N log K)	O(K)	Large N, small K
QuickSelect	O(N) avg	O(1)	Single Kth element, in-memory
Counting Sort	O(N)	O(range)	Bounded integers only

When K ≪ N, log K ≪ log N — heap is significantly faster than sorting.

TypeScript

Implementation

From scratch, with detailed comments.

// A Min-Heap that holds at most `capacity` elements.
// The smallest value always lives at index 0 (the root).
class MinHeap {
  private heap: number[] = [];

  constructor(private capacity: number) {}

  insert(val: number) {
    if (this.heap.length < this.capacity) {
      this.heap.push(val);
      this.heapifyUp();              // bubble new element up
    } else if (val > this.heap[0]) {
      // new value beats the current minimum → replace it
      this.heap[0] = val;
      this.heapifyDown();             // sink new root down
    }
  }

  getTopK(): number[] { return [...this.heap]; }

  private heapifyUp() {
    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] >= this.heap[parent]) break; // heap ok
      [this.heap[i], this.heap[parent]] =
        [this.heap[parent], this.heap[i]];   // swap
      i = parent;
    }
  }

  private heapifyDown() {
    let i = 0;
    while (true) {
      const left  = 2 * i + 1;
      const right = 2 * i + 2;
      let   min   = i;

      if (left  < this.heap.length && this.heap[left]  < this.heap[min]) min = left;
      if (right < this.heap.length && this.heap[right] < this.heap[min]) min = right;
      if (min === i) break;                    // heap ok

      [this.heap[i], this.heap[min]] =
        [this.heap[min], this.heap[i]];
      i = min;
    }
  }
}

// O(N log K) — only ever keeps K elements in memory
function findTopKElements(arr: number[], k: number): number[] {
  const minHeap = new MinHeap(k);
  for (const num of arr) {
    minHeap.insert(num);   // O(log K) per insert
  }
  return minHeap.getTopK();
}

// Test
const numbers = [10, 4, 5, 8, 6, 11, 26, 2];
const k = 3;
console.log(findTopKElements(numbers, k));
// → [26, 11, 10]  (top 3 largest)

// LeetCode 347: Top K Frequent Elements
function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  // min-heap ordered by frequency
  const heap: [number, number][] = []; // [freq, num]
  for (const [num, cnt] of freq) {
    heap.push([cnt, num]);
    heap.sort((a, b) => a[0] - b[0]);
    if (heap.length > k) heap.shift();
  }
  return heap.map(h => h[1]);
}

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

// Simple sorting approach — O(N log N)
// Sorts the ENTIRE array even when K=3 and N=10,000,000
function topKWithSorting(arr: number[], k: number): number[] {
  return [...arr]
    .sort((a, b) => b - a)  // descending
    .slice(0, k);
}

const numbers = [10, 4, 5, 8, 6, 11, 26, 2];
console.log(topKWithSorting(numbers, 3));
// → [26, 11, 10]

// When is sorting acceptable?
// ✓ N is small (< 1000)
// ✓ You need all elements sorted anyway
// ✓ Quick interview prototype
// ✗ Large datasets (N in millions)
// ✗ Streaming / real-time data
// ✗ Memory-sensitive environments

Comparison

Heap vs Array

📦 Regular Array O(N log N)

Access top O(1) (if sorted)

Insert O(1) unsorted · O(N) sorted

Find top K Sort first → O(N log N)

Memory O(N) — stores everything

Real-time stream Re-sort on every insert

🪄 Min-Heap (K-size) O(N log K)

Access min O(1) — always at root

Insert / update O(log K)

Find top K O(N log K) — no full sort

Memory O(K) — only K elements

Real-time stream Insert each new value O(log K)

Practice

Solve It Yourself

Click any question to see hints and approach.

B Basic

B1 Given [7, 10, 4, 3, 20, 15] and K=3, find the top 3 largest elements using a Min-Heap. ⌄

💡 Hint

Build a min-heap of size 3. For each remaining element, if it's larger than the root, replace the root and heapifyDown.

✅ Answer

Result: [20, 15, 10]. Heap after processing: [10, 15, 20] (min at root).

B2 Explain why a Min-Heap is preferred over a Max-Heap for finding the Top K largest elements. ⌄

💡 Hint

With a min-heap of size K, the root is always the current Kth largest — you compare each new element against it in O(1).

✅ Answer

A min-heap of size K keeps the K largest elements. The root (minimum of the K) is the gate: anything larger gets in, anything smaller is discarded. A max-heap would need to hold all N elements.

B3 What does array index i=2 represent in a binary heap stored in an array? What are its parent, left child, and right child indices? ⌄

💡 Hint

Use the index formulas: parent = ⌊(i−1)/2⌋, left = 2i+1, right = 2i+2.

✅ Answer

Parent: ⌊(2−1)/2⌋ = 0. Left child: 2×2+1 = 5. Right child: 2×2+2 = 6.

M Intermediate

M1 LeetCode 215 — Kth Largest Element in an Array: find the 2nd largest in [5, 3, 8, 2, 10, 7]. ⌄

💡 Hint

Use a min-heap of size K=2. After processing all elements the root is the Kth largest.

✅ Answer

Answer: 8. Heap after all inserts: [8, 10] → root (8) is the 2nd largest.

→ Solve on LeetCode ↗

M2 LeetCode 347 — Top K Frequent Elements: given [1,1,1,2,2,3,3,3,3] and K=2, find the 2 most frequent elements. ⌄

💡 Hint

Build a frequency map first (O(N)), then run a min-heap of size K on (frequency, element) pairs.

✅ Answer

Answer: [3, 1] — 3 appears 4 times, 1 appears 3 times. Time: O(N log K).

→ Solve on LeetCode ↗

M3 LeetCode 658 — Find K Closest Numbers: given [1,3,7,8,9,10] and target=6, K=3, find 3 numbers closest to 6. ⌄

💡 Hint

Use a max-heap on |num − target|. Keep heap size ≤ K; if a new element is closer than the farthest one, replace it.

✅ Answer

Answer: [7, 8, 9] — distances are 1, 2, 3 from target 6. Max-heap on distance works here.

→ Solve on LeetCode ↗

H Advanced

H1 LeetCode 239 — Sliding Window Maximum: [1,3,−1,−3,5,3,6,7], window=3. Find max in each window. ⌄

💡 Hint

A deque (monotonic decreasing) is O(N). A heap also works at O(N log K). Track which elements are still in the window.

✅ Answer

Output: [3,3,5,5,6,7]. Deque approach: maintain indices of decreasing values; front is always the max of current window.

→ Solve on LeetCode ↗

H2 LeetCode 23 — Merge K Sorted Lists: merge K sorted linked lists into one sorted list. ⌄

💡 Hint

Use a min-heap of size K containing (value, listIndex, nodePointer). Poll the min node, add to result, push its next node.

✅ Answer

Time: O(N log K) where N = total nodes. Each heap operation costs O(log K), done N times.

→ Solve on LeetCode ↗

H3 Design a KthLargest class that supports add(num) and always returns the Kth largest in the stream. ⌄

💡 Hint

Maintain a min-heap of size exactly K. add() inserts and possibly pops smallest; root is always the Kth largest.

✅ Answer

class KthLargest { constructor(k, nums) { this.k=k; this.heap=[]; for(n of nums) this.add(n); } add(val) { /* insert + trim to k */ return this.heap[0]; } }

→ Solve on LeetCode ↗

H4 Top K Frequent Words: return the top K most frequently occurring words. Tie-break: lexicographically smaller word wins. ⌄

💡 Hint

Build a frequency map, then use a min-heap that orders by (frequency ASC, word DESC) — so ties are broken by reverse-lex, and the winner is at root.

✅ Answer

For ['the','the','a','is','a'], K=2 → ['the','a']. Heap comparator: (a,b) => freq[a]!==freq[b] ? freq[a]-freq[b] : b.localeCompare(a).

→ Solve on LeetCode ↗

In the Wild

Real-World Applications

🔍

Google Search

Top-K Relevant Pages

From billions of indexed pages, Google's ranking pipeline surfaces the top K most relevant results per query. Heap-based selection avoids sorting the entire index.

🪄 How Heap Fits: Min-heap of K pages ranked by relevance score. Process N candidates in O(N log K).

🐦

Twitter / X

Trending Hashtags

Every few minutes, Twitter aggregates billions of tweets and surfaces the top 10 trending hashtags per region.

🪄 How Heap Fits: Frequency map + K-size min-heap per region. Real-time streaming with heap updates.

🎬

Netflix

Top K Trending Shows

Netflix's recommendation engine finds top K titles by views/engagement score to populate the 'Trending Now' row.

🪄 How Heap Fits: Min-heap over millions of title scores. O(N log K) instead of sorting the catalog.

▶️

YouTube

Most-Viewed Videos

The 'Top videos' leaderboard tracks the K videos with the highest view counts, updating as new views arrive in a stream.

🪄 How Heap Fits: KthLargest pattern: insert each view event; heap root is always the Kth most-viewed threshold.

Quick Reference

Cheat Sheet

Array Index Formulas

Parent of node i

⌊(i − 1) / 2⌋

Left child

2 × i + 1

Right child

2 × i + 2

Root

index 0

When to Use Heap

✓ Top K largest elements
✓ Top K smallest elements
✓ Kth largest / smallest
✓ K most frequent elements
✓ K closest to a target
✓ Merge K sorted lists
✓ Sliding window max/min
✓ Real-time data streams

Min vs Max Heap

Min-Heap (size K)

→ Find Top K LARGEST

Root = Kth largest (gate value)

Max-Heap (size K)

→ Find Top K SMALLEST

Root = Kth smallest (gate value)

Complexity

Time: O(N log K)

Space: O(K)

Keep Learning

You've mastered Top K Elements 🎉

This pattern appears in 30+ LeetCode problems. Now practice it until it's automatic.

← Back to Learn LeetCode Heap Problems ↗