DATA STRUCTURES PROGRAM • HEAPS, HASHING & DISJOINT SETS
Find the Kth-Largest Value with a Min-Heap
Learn how to find the kth-largest value with a min-heap using a clear C program.
PROBLEM UNDERSTANDING
Input and expected output
Sample input
No input required
Sample output
3rd largest = 10
COMPLETE C PROGRAM
Complete C implementation
#include <stdio.h>
void sift_up(int heap[], int position)
{
while (position > 0) {
int parent = (position - 1) / 2;
if (heap[parent] <= heap[position]) return;
int temporary = heap[parent]; heap[parent] = heap[position]; heap[position] = temporary;
position = parent;
}
}
void sift_down(int heap[], int size, int position)
{
while (1) {
int smallest = position, left = 2 * position + 1, right = left + 1;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest == position) return;
int temporary = heap[position]; heap[position] = heap[smallest]; heap[smallest] = temporary;
position = smallest;
}
}
int main(void)
{
int values[] = {7, 10, 4, 3, 20, 15};
int heap[3], size = 0, k = 3;
for (int index = 0; index < 6; index++) {
if (size < k) {
heap[size] = values[index];
sift_up(heap, size++);
} else if (values[index] > heap[0]) {
heap[0] = values[index];
sift_down(heap, size, 0);
}
}
printf("3rd largest = %d\n", heap[0]);
return 0;
}CURRENT STEP
SELECTED LINE
EXPECTED OUTPUT FOR THE SAMPLE
3rd largest = 10
Step 0 of 0
PROGRAM EXPLANATION
Algorithm and explanation
- Read the required input values.
- Keep only the k largest values; the smallest retained value is the kth largest.
- Display the computed result.
Keep only the k largest values; the smallest retained value is the kth largest.
EFFICIENCY
Time and space complexity
Time complexity
O(n log k)
Auxiliary space
O(k)
DEBUGGING CHECKLIST
Common mistakes
Check this
Use the correct format specifier for every variable.
Check this
Initialize variables before using their values.
Check this
Check braces, semicolons and input order carefully.
Try it yourself
Practice: Run the program with the sample input, predict its output, and then test one boundary case of your own.
