मान लीजिए हमारे पास कुछ सूचियाँ हैं, ये सूचियाँ सॉर्ट की गई हैं। हमें इन सूचियों को एक सूची में मर्ज करना है। इसे हल करने के लिए, हम हीप डेटा संरचना का उपयोग करेंगे। इसलिए यदि सूचियाँ [1,4,5], [1,3,4], [2,6] हैं, तो अंतिम सूची [1,1,2,3,4,4,5,6] होगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- n := lists का आकार
- heap := एक नई सूची
- प्रत्येक इंडेक्स i और lists[i] की पंक्ति के लिए, करें
- यदि पंक्ति खाली नहीं है, तो
- (row[0], i, 0) को heap में डालें
- यदि पंक्ति खाली नहीं है, तो
- res := एक नई सूची
- जब तक heap खाली नहीं है, करें
- num, row, col := heap का शीर्ष तत्व
- num को res के अंत में जोड़ें
- यदि col < lists[row] का आकार - 1, तो
- (lists[row, col + 1], row, col + 1) को heap में डालें
- res वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
import heapq class Solution: def solve(self, lists): n = len(lists) heap = [] for i, row in enumerate(lists): if row: heapq.heappush(heap, (row[0], i, 0)) res = [] while heap: num, row, col = heapq.heappop(heap) res.append(num) if col < len(lists[row]) - 1: heapq.heappush(heap, (lists[row][col + 1], row, col + 1)) return res ob = Solution() lists = [[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]] print(ob.solve(lists))
इनपुट
[[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]
आउटपुट
[1, 4, 4, 4, 8, 11, 11, 13, 14]
