K सबसे बड़े Elements

k largest ढूंढना top k scores का एक छोटा leaderboard रखने जैसा है: एक नया score सिर्फ तब join करता है जब यह board पर सबसे कम एक को हराए।

In this page:

Problem Idea
Min Heap Method
Remove Small Values
Complexity
Practice

Syntax

markup

import heapq
heap = []
for x in arr:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)    # drop the smallest
# heap now holds the k largest

Problem Idea

किसी array में k largest values ढूंढने के लिए पूरी चीज़ sort करने की ज़रूरत नहीं — k size का एक min heap एक बार data scan करते समय सिर्फ top k values track करने का एक efficient तरीका देता है।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3, 1, 5, 12, 2, 8};
	int n = 6, k = 3;
	cout << "Need top " << k << " largest of " << n << " values without sorting all of them";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {3, 1, 5, 12, 2, 8};
		int n = 6, k = 3;
		System.out.println("Need top " + k + " largest of " + n + " values without sorting all of them");
	}
}

arr = [3, 1, 5, 12, 2, 8]
n, k = 6, 3
print(f"Need top {k} largest of {n} values without sorting all of them")

#include <stdio.h>
int main() {
	int arr[] = {3, 1, 5, 12, 2, 8};
	int n = 6, k = 3;
	printf("Need top %d largest of %d values without sorting all of them", k, n);
	return 0;
}

Min Heap Method

Idea है ज़्यादा से ज़्यादा k elements वाला एक min heap maintain करना: array scan करते समय, अगर heap में k से कम elements हों, नई value जोड़ें; एक बार यह full हो जाए, सिर्फ तब नई value जोड़ें अगर यह heap की current minimum से बड़ी हो, उस minimum को replace करते हुए।

उदाहरण: Min Heap Method

#include <iostream>
#include <queue>
using namespace std;
int main() {
	int arr[] = {3, 1, 5, 12, 2, 8};
	int k = 3;
	priority_queue<int, vector<int>, greater<int>> heap;
	for (int x : arr) {
		if ((int)heap.size() < k) heap.push(x);
		else if (x > heap.top()) { heap.pop(); heap.push(x); }
	}
	cout << "Heap has " << heap.size() << " elements after scanning all " << 6;
	return 0;
}

import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) {
		int[] arr = {3, 1, 5, 12, 2, 8};
		int k = 3;
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		for (int x : arr) {
			if (heap.size() < k) heap.add(x);
			else if (x > heap.peek()) { heap.poll(); heap.add(x); }
		}
		System.out.println("Heap has " + heap.size() + " elements after scanning all 6");
	}
}

import heapq
arr = [3, 1, 5, 12, 2, 8]
k = 3
heap = []
for x in arr:
    if len(heap) < k:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)
print(f"Heap has {len(heap)} elements after scanning all 6")

#include <stdio.h>
int main() {
	int arr[] = {3, 1, 5, 12, 2, 8};
	int k = 3, heap[3], size = 0;
	for (int i = 0; i < 6; i++) {
		if (size < k) heap[size++] = arr[i];
		else {
			int minIdx = 0;
			for (int j = 1; j < k; j++) if (heap[j] < heap[minIdx]) minIdx = j;
			if (arr[i] > heap[minIdx]) heap[minIdx] = arr[i];
		}
	}
	printf("Heap has %d elements after scanning all 6", size);
	return 0;
}

Remove Small Values

चूंकि min heap हमेशा अपनी tracked सबसे छोटी value root पर रखता है, एक नए element को root से compare करना तुरंत बताता है कि यह current top k में belong करता है या सुरक्षित रूप से ignore किया जा सकता है — k largest में से सबसे छोटे को जगह बनाने के लिए हटाया जाता है।

उदाहरण: Remove Small Values

#include <iostream>
#include <queue>
using namespace std;
int main() {
	priority_queue<int, vector<int>, greater<int>> heap;
	heap.push(3); heap.push(1); heap.push(5);
	int newVal = 8;
	if (newVal > heap.top()) {
		cout << "Root " << heap.top() << " removed, " << newVal << " kept";
		heap.pop(); heap.push(newVal);
	}
	return 0;
}

import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) {
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		heap.add(3); heap.add(1); heap.add(5);
		int newVal = 8;
		if (newVal > heap.peek()) {
			System.out.println("Root " + heap.peek() + " removed, " + newVal + " kept");
			heap.poll(); heap.add(newVal);
		}
	}
}

import heapq
heap = []
for v in [3, 1, 5]:
    heapq.heappush(heap, v)
new_val = 8
if new_val > heap[0]:
    print(f"Root {heap[0]} removed, {new_val} kept")
    heapq.heapreplace(heap, new_val)

#include <stdio.h>
int main() {
	int heap[3] = {1, 3, 5};
	int newVal = 8, minIdx = 0;
	for (int j = 1; j < 3; j++) if (heap[j] < heap[minIdx]) minIdx = j;
	if (newVal > heap[minIdx]) {
		printf("Root %d removed, %d kept", heap[minIdx], newVal);
		heap[minIdx] = newVal;
	}
	return 0;
}

Complexity

यह approach O(n log k) time में चलता है, क्योंकि n elements में से हर एक ज़्यादा से ज़्यादा एक O(log k) heap operation करता है, और heap के लिए सिर्फ O(k) extra space उपयोग करता है — जब k, n से कहीं छोटा हो तो O(n log n) time में पूरे array को sort करने पर एक meaningful improvement।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "K largest via min heap: O(n log k) time, O(k) extra space";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("K largest via min heap: O(n log k) time, O(k) extra space");
	}
}

print("K largest via min heap: O(n log k) time, O(k) extra space")

#include <stdio.h>
int main() {
	printf("K largest via min heap: O(n log k) time, O(k) extra space");
	return 0;
}

Practice

यह 'top k', 'k closest', या 'k most frequent' मांगने वाली problems में एक आम pattern है — यह पहचानना कि आपको सिर्फ k size का heap चाहिए, सब कुछ का एक पूरा sort नहीं, अक्सर वह key insight है जो एक अन्यथा धीमे solution को fast बनाती है।

उदाहरण: Practice

#include <iostream>
#include <queue>
using namespace std;
int main() {
	// "k closest points", "k most frequent words" all reuse this same size-k heap pattern
	int arr[] = {4, 9, 1, 6, 3, 7};
	int k = 2;
	priority_queue<int, vector<int>, greater<int>> heap;
	for (int x : arr) {
		if ((int)heap.size() < k) heap.push(x);
		else if (x > heap.top()) { heap.pop(); heap.push(x); }
	}
	cout << "Top " << k << " smallest tracked value: " << heap.top();
	return 0;
}

import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 9, 1, 6, 3, 7};
		int k = 2;
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		for (int x : arr) {
			if (heap.size() < k) heap.add(x);
			else if (x > heap.peek()) { heap.poll(); heap.add(x); }
		}
		System.out.println("Top " + k + " smallest tracked value: " + heap.peek());
	}
}

import heapq
arr = [4, 9, 1, 6, 3, 7]
k = 2
heap = []
for x in arr:
    if len(heap) < k:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)
print(f"Top {k} smallest tracked value: {heap[0]}")

#include <stdio.h>
int main() {
	int arr[] = {4, 9, 1, 6, 3, 7};
	int k = 2, heap[2], size = 0;
	for (int i = 0; i < 6; i++) {
		if (size < k) heap[size++] = arr[i];
		else {
			int minIdx = 0;
			for (int j = 1; j < k; j++) if (heap[j] < heap[minIdx]) minIdx = j;
			if (arr[i] > heap[minIdx]) heap[minIdx] = arr[i];
		}
	}
	int minIdx = 0;
	for (int j = 1; j < k; j++) if (heap[j] < heap[minIdx]) minIdx = j;
	printf("Top %d smallest tracked value: %d", k, heap[minIdx]);
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Heap Sort Next Lesson → Merge K Sorted Lists