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

K-way Merge

7 min Intermediate 7 steps

Merge k sorted lists with a min-heap of heads.

K
3 lists
N
8 values
Each list
sorted
LIST A145LIST B134LIST C26merge into one sorted list
current done skipped
In this lessonStep 1 of 7
  1. The problem
  2. Heap of heads
  3. Pop, push
  4. Full merge
  5. Matrix
  6. Alternatives
  7. Recap
Step 1 / 7problem

Three sorted lists, one sorted output

Merge [1, 4, 5], [1, 3, 4] and [2, 6] into one sorted list.

Each list is already sorted, so the next value of the output must be the smallest of the current heads. Everything behind a head can wait.

Key idea

K sorted lists, arrays or streams that need one merged order, the kth element, or a range across all: think K-way merge.

←→ step·R replay·Space pause

You'll learn

  • See why only the K heads can be next
  • Run the heap-of-heads merge: pop, output, push next
  • Stop after k pops for the kth smallest in a sorted matrix
  • Compare heap, divide and conquer, and fold left
Read the full notesTrees, Graphs and Search, 8