Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Tree BFS
  • Tree DFS
  • Two Heaps
  • Top K Elements
  • K-way Merge
  • Trie
Learn/Data Structures & Algorithms/Trees & Heaps

Top K Elements

7 min Intermediate 8 steps

A size-k heap beats sorting everything.

n
6
k
2
Want
kth largest
321564find the 2nd largest of [3, 2, 1, 5, 6, 4]
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. Min-heap
  3. Push, pop
  4. The answer
  5. Frequent
  6. Options
  7. Buckets
  8. Recap
Step 1 / 8problem

Sorting everything to read one slot

Find the 2nd largest in [3, 2, 1, 5, 6, 4].

Sorting works, but it orders all n elements when you only care about the top k. When n is large and k is small, that is wasted work.

Key idea

K largest, K smallest, K most frequent, K closest, kth largest: think Top K with a heap.

←→ step·R replay·Space pause

You'll learn

  • Use a heap of the opposite kind, capped at size K
  • Read the kth largest from the top of the heap
  • Apply it to frequencies with a count map
  • Compare sort, heap, quickselect and bucket sort
Read the full notesTrees, Graphs and Search, 7