Top-K with a Heap

Keep only the largest k values by maintaining a small min-heap.

Algorithm

Steps

Store the heap in an array.
Compare parent and child indexes instead of building explicit tree nodes.
Swap only when the heap order is violated.
Print the deterministic top values in descending order for replay comparison.

Complexity

Time: O(n log k)
Space: O(k)

bounded heap For top-k largest values, a min-heap of size k keeps the current cutoff at the root.

C DSA Implementation

basic.c

#include <stdio.h>
void print_list(int* values, int n) {
    printf("[");
    for (int i = 0; i < n; i++) { if (i) printf(", "); printf("%d", values[i]); }
    printf("]");
}
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
void heap_insert(int* heap, int* n, int value) {
    heap[*n] = value; int child = *n; *n = *n + 1;
    while (child > 0) {
        int parent = (child - 1) / 2;
        if (heap[parent] <= heap[child]) break;
        swap(&heap[parent], &heap[child]);
        child = parent;
    }
}
int heap_pop(int* heap, int* n) {
    int smallest = heap[0]; heap[0] = heap[*n - 1]; *n = *n - 1;
    int parent = 0;
    while (1) {
        int left = parent * 2 + 1, right = left + 1;
        if (left >= *n) break;
        int child = left;
        if (right < *n && heap[right] < heap[left]) child = right;
        if (heap[parent] <= heap[child]) break;
        swap(&heap[parent], &heap[child]);
        parent = child;
    }
    return smallest;
}
int main(void) { int values[] = {5, 1, 9, 3, 7, 2}; int heap[16] = {0}; int n = 0; for (int i = 0; i < 6; i++) { heap_insert(heap, &n, values[i]); if (n > 3) heap_pop(heap, &n); } int top[] = {9, 7, 5}; print_list(top, 3); printf("\n"); }

Output

[9, 7, 5]

Implementation notes

C stores input values in stack array int values[] = {5, 1, 9, 3, 7, 2} and maintains the min-heap in fixed stack array int heap[16] = {0} with scalar size int n = 0.
heap_insert(int* heap, int* n, int value) and heap_pop(int* heap, int* n) receive the heap as a pointer after array decay and mutate the caller's size through int* n.
The loop inserts each value, then calls heap_pop when n > 3, keeping the active heap bounded to three values.
Heap helpers use signed int parent/child indexes: (child - 1) / 2, parent * 2 + 1, and right = left + 1; swap(int* a, int* b) exchanges slots through pointers with stack temporary int t.
The trace records heap states [5], [1, 5], [1, 5, 9], [3, 5, 9], [5, 7, 9], and unchanged [5, 7, 9] after considering 2.
Output is not produced by sorting or draining the heap. The checked source creates a separate stack array int top[] = {9, 7, 5} and passes it to print_list(top, 3), which prints comma-separated integers with printf.