K way merge

Question 1

What is K-way Merge?

Answer 1

K-way Merge merges k sorted lists using a min heap.

Use Case: Merge sorted arrays, external sorting.

Example: Merge K Sorted Lists.

Question 2

What are the key steps in K-way Merge?

Answer 2

1. Initialize min heap with first elements.
2. Pop smallest, add next from same list.
3. Repeat until heap empty.

Action: Explain steps for Merge K Sorted Lists aloud.

Question 3

How does K-way Merge apply to Merge K Sorted Lists?

Answer 3

The problem is to merge k sorted linked lists. The approach is to use a min heap to select the smallest node across lists.

Example: Merge K Sorted Lists.

Question 4

What are the complexity and gotchas of K-way Merge?

Answer 4

Time complexity is O(n log k) and space complexity is O(k).
Gotchas include handling empty lists and single lists.

Action: List edge cases for Merge K Sorted Lists aloud.

Question 5

Code example for K-way Merge.

Answer 5

```python
from typing import List, Optional
from heapq import heappush, heappop
class ListNode:
def __init__(self, val: int = 0, next: ‘ListNode’ = None):
self.val = val
self.next = next
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode(0)
current = dummy
heap: List[tuple[int, ListNode]] = []
for i, node in enumerate(lists):
if node:
heappush(heap, (node.val, i, node))
while heap:
val, i, node = heappop(heap)
current.next = node
current = current.next
if node.next:
heappush(heap, (node.next.val, i, node.next))
return dummy.next
~~~

Action: Sketch heap merging on paper.