K Sorted Lists को Merge करना

k sorted lists merge करना kids की कई sorted lines को एक में combine करने जैसा है, हमेशा किसी भी line के front से shortest kid चुनते हुए।

In this page:

Problem Idea
Heap Approach
Process Minimum
Complexity
Practice

Syntax

markup

import heapq
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)
while heap:
    value, i, j = heapq.heappop(heap)
    result.append(value)
    if j + 1 < len(lists[i]):
        heapq.heappush(heap, (lists[i][j + 1], i, j + 1))

Problem Idea

यह problem आपसे k अलग sorted lists को एक पूरी तरह sorted list में combine करने को कहती है — simpler two-list merge का एक generalization, जहां हर step पर naively सभी k lists में compare करना अनावश्यक रूप से धीमा होगा।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
	cout << "Merging 3 sorted lists into one fully sorted output, not just two at a time";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
		System.out.println("Merging 3 sorted lists into one fully sorted output, not just two at a time");
	}
}

lists = [[1, 4], [2, 5], [3, 6]]
print("Merging 3 sorted lists into one fully sorted output, not just two at a time")

#include <stdio.h>
int main() {
	int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
	printf("Merging 3 sorted lists into one fully sorted output, not just two at a time");
	return 0;
}

Heap Approach

एक min heap इसे efficiently एक समय में k lists में से हर एक का सिर्फ एक candidate value रखकर solve करता है — हर list का current front — इसलिए सभी lists में overall सबसे छोटी अगली value हमेशा heap के root पर available है।

उदाहरण: Heap Approach

#include <iostream>
#include <queue>
using namespace std;
int main() {
	vector<vector<int>> lists = {{1, 4}, {2, 5}, {3, 6}};
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
	for (int i = 0; i < 3; i++) heap.push({lists[i][0], i});
	cout << "Heap holds one front value per list, smallest overall on top: " << heap.top().first;
	return 0;
}

import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) {
		int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
		PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < 3; i++) heap.add(new int[]{lists[i][0], i});
		System.out.println("Heap holds one front value per list, smallest overall on top: " + heap.peek()[0]);
	}
}

import heapq
lists = [[1, 4], [2, 5], [3, 6]]
heap = [(lists[i][0], i, 0) for i in range(3)]
heapq.heapify(heap)
print(f"Heap holds one front value per list, smallest overall on top: {heap[0][0]}")

#include <stdio.h>
int main() {
	int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
	int minVal = lists[0][0], minList = 0;
	for (int i = 1; i < 3; i++) if (lists[i][0] < minVal) { minVal = lists[i][0]; minList = i; }
	printf("Heap holds one front value per list, smallest overall on top: %d", minVal);
	return 0;
}

Process Minimum

हर step heap से minimum हटाता है, इसे output में append करता है, और फिर जिस भी list से वह minimum आया उससे अगली value push करता है — यह हर समय heap में हर अब भी active list के लिए बिल्कुल एक value रखता है।

उदाहरण: Process Minimum

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
	vector<vector<int>> lists = {{1, 4}, {2, 5}, {3, 6}};
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
	vector<int> idx(3, 0);
	for (int i = 0; i < 3; i++) heap.push({lists[i][0], i});
	vector<int> output;
	while (!heap.empty()) {
		auto [val, li] = heap.top(); heap.pop();
		output.push_back(val);
		idx[li]++;
		if (idx[li] < (int)lists[li].size()) heap.push({lists[li][idx[li]], li});
	}
	for (int v : output) cout << v << " ";
	return 0;
}

import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) {
		int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
		int[] idx = {0, 0, 0};
		PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < 3; i++) heap.add(new int[]{lists[i][0], i});
		StringBuilder out = new StringBuilder();
		while (!heap.isEmpty()) {
			int[] top = heap.poll();
			out.append(top[0]).append(" ");
			idx[top[1]]++;
			if (idx[top[1]] < lists[top[1]].length) heap.add(new int[]{lists[top[1]][idx[top[1]]], top[1]});
		}
		System.out.println(out.toString().trim());
	}
}

import heapq
lists = [[1, 4], [2, 5], [3, 6]]
heap = [(lists[i][0], i, 0) for i in range(3)]
heapq.heapify(heap)
output = []
while heap:
    val, li, ei = heapq.heappop(heap)
    output.append(val)
    if ei + 1 < len(lists[li]):
        heapq.heappush(heap, (lists[li][ei + 1], li, ei + 1))
print(*output)

#include <stdio.h>
int main() {
	int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
	int idx[3] = {0, 0, 0}, output[6], n = 0;
	for (int step = 0; step < 6; step++) {
		int minVal = 1000000, minList = -1;
		for (int i = 0; i < 3; i++)
			if (idx[i] < 2 && lists[i][idx[i]] < minVal) { minVal = lists[i][idx[i]]; minList = i; }
		output[n++] = minVal;
		idx[minList]++;
	}
	for (int i = 0; i < n; i++) printf("%d ", output[i]);
	return 0;
}

Complexity

k lists और उन सभी में कुल n values के साथ, यह heap-based approach O(n log k) time में चलता है, क्योंकि n values में से हर एक एक O(log k) heap operation trigger करती है — lists को बार-बार pairwise merge करने से कहीं बेहतर, जो overall ज़्यादा comparisons की कीमत लेता है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Merge k sorted lists: O(n log k) time with n total values, O(k) heap space";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space");
	}
}

print("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space")

#include <stdio.h>
int main() {
	printf("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space");
	return 0;
}

Practice

Core discipline हर step पर सही true global minimum लेकर output को हर step पर सही से sorted रखना है, जो बिल्कुल वही है जो min heap बिना हर step पर सीधे सभी k lists में compare करने की ज़रूरत के गारंटी देता है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Always pull the true global minimum next -- that discipline is what keeps output sorted";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Always pull the true global minimum next -- that discipline is what keeps output sorted");
	}
}

print("Always pull the true global minimum next -- that discipline is what keeps output sorted")

#include <stdio.h>
int main() {
	printf("Always pull the true global minimum next -- that discipline is what keeps output sorted");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson K Largest Elements Next Lesson → Graph Introduction