K-way Merge

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 कहाँ से लाना है)।

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' जैसी समस्याओं में इस्तेमाल होता है।