K Largest Elements
In this page:
Problem Idea
Finding the k largest values in an array doesn't require sorting the entire thing — a min heap of size k gives an efficient way to track just the top k values as you scan through the data once.
Example: 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;
}Login to try C/C++/Java code in the editor
Min Heap Method
The idea is to maintain a min heap containing at most k elements: as you scan the array, if the heap has fewer than k elements, add the new value; once it's full, only add a new value if it's larger than the heap's current minimum, replacing that minimum.
Example: 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;
}Login to try C/C++/Java code in the editor
Remove Small Values
Because the min heap always keeps its smallest tracked value at the root, comparing a new element against the root immediately tells you whether it belongs among the current top k or can be safely ignored — the smallest of the k largest is removed to make room.
Example: 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;
}Login to try C/C++/Java code in the editor
Complexity
This approach runs in O(n log k) time, since each of the n elements does at most one O(log k) heap operation, and uses only O(k) extra space for the heap — a meaningful improvement over sorting the entire array in O(n log n) time when k is much smaller than n.
Example: 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;
}Login to try C/C++/Java code in the editor
Practice
This is a common pattern in problems that ask for 'top k', 'k closest', or 'k most frequent' — recognizing that you only need a heap sized to k, not a full sort of everything, is often the key insight that makes an otherwise slow solution fast.
Example: 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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: