# K-way Merge — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/k-way-merge

> एक min-heap का उपयोग करते हुए k sorted lists को कुशलता से मिलाएँ, जो हर list से अगला-सबसे-छोटा उम्मीदवार रखता है।

## Two-way merge से आगे

दो sorted lists को मिलाना दो pointers से `O(n)` है। **k** sorted lists के लिए, हर list से एक उम्मीदवार रखने वाला **min-heap** इसे सामान्यीकृत करता है: हमेशा सबसे छोटा pop करें, फिर उस list का अगला element push करें।

## k sorted lists मिलाएँ

Heap को हर list के पहले element से भरें (उसके list/index के साथ चिह्नित ताकि पता चले अगला value कहाँ से लाना है)।

```python
import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result
```

Output:

```
merge_k_sorted([[1,4,5],[1,3,4],[2,6]])
# [1, 1, 2, 3, 4, 4, 5, 6]
```

## Complexity और उपयोग

`k` lists में कुल `n` elements के साथ, यह `O(n log k)` में चलता है — heap में कभी `k` से ज़्यादा elements नहीं होते। Sorted log files मिलाने, external sorting, और 'k lists को कवर करने वाली सबसे छोटी range' जैसी समस्याओं में इस्तेमाल होता है।