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

अंतिम क्विज़ 1/8

अंतिम क्विज़

त्वरित जाँच: Binary search की time complexity क्या है?

• O(n)
• O(1)
• O(log n)
• O(n log n)

अंतिम क्विज़ 2/8

अंतिम क्विज़

त्वरित जाँच: कौन-सी structure key से औसत O(1) lookup देती है?

• Linked list
• Stack
• Sorted array scan
• Hash map

अंतिम क्विज़ 3/8

अंतिम क्विज़

त्वरित जाँच: Balanced-bracket जाँच के लिए कौन-सी structure उपयुक्त है?

• Stack
• Queue
• Trie
• Heap

अंतिम क्विज़ 4/8

अंतिम क्विज़

त्वरित जाँच: Unweighted graph में shortest paths कौन-सा traversal खोजता है?

• DFS
• BFS
• In-order
• Post-order

अंतिम क्विज़ 5/8

अंतिम क्विज़

त्वरित जाँच: Dijkstra का algorithm कब सही परिणाम देता है?

• The graph is a tree
• The graph is undirected
• All edge weights are non-negative
• The graph is small

अंतिम क्विज़ 6/8

अंतिम क्विज़

त्वरित जाँच: Merge sort का worst-case time क्या है?

• O(n^2)
• O(n)
• O(log n)
• O(n log n)

अंतिम क्विज़ 7/8

अंतिम क्विज़

त्वरित जाँच: Longest-substring समस्याओं को एक pass में कौन-सा pattern संभालता है?

• Sliding window
• Union-find
• Bit manipulation
• K-way merge

अंतिम क्विज़ 8/8

अंतिम क्विज़

त्वरित जाँच: कौन-सी बात किसी समस्या को dynamic programming के उपयुक्त बनाती है?

• Random inputs
• Overlapping subproblems and optimal substructure
• Large strings
• Sorted data