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 final heap state 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.cpp

#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
void heapInsert(vector<int>& heap, int value) {
    heap.push_back(value);
    size_t child = heap.size() - 1;
    while (child > 0) {
        size_t parent = (child - 1) / 2;
        if (heap[parent] <= heap[child]) break;
        swap(heap[parent], heap[child]);
        child = parent;
    }
}
int heapPop(vector<int>& heap) {
    int smallest = heap[0];
    heap[0] = heap.back(); heap.pop_back();
    size_t parent = 0;
    while (true) {
        size_t left = parent * 2 + 1, right = left + 1;
        if (left >= heap.size()) break;
        size_t child = left;
        if (right < heap.size() && heap[right] < heap[left]) child = right;
        if (heap[parent] <= heap[child]) break;
        swap(heap[parent], heap[child]);
        parent = child;
    }
    return smallest;
}
int main() { vector<int> heap; for (int value : {5, 1, 9, 3, 7, 2}) { heapInsert(heap, value); if (heap.size() > 3) heapPop(heap); } sort(heap.begin(), heap.end(), greater<int>()); cout << listString(heap) << "\n"; }

Output

[9, 7, 5]

Implementation notes

In C++, main starts with an empty std::vector<int> heap and iterates the input values from the braced list {5, 1, 9, 3, 7, 2} as copied ints.
heapInsert(vector<int>& heap, int value) and heapPop(vector<int>& heap) mutate the same vector by reference; heapInsert uses push_back, and heapPop replaces the root with back() before pop_back().
The fixed size is enforced after each insert with if (heap.size() > 3) heapPop(heap), so the trace keeps only three slots once the fourth value is considered.
Heap navigation uses size_t indexes: parent (child - 1) / 2, left child parent * 2 + 1, and right child left + 1. Swaps use std::swap on vector elements during sift-up and sift-down.
The replayed heap states are [5], [1, 5], [1, 5, 9], [3, 5, 9], [5, 7, 9], and unchanged [5, 7, 9] after considering 2.
sort(heap.begin(), heap.end(), greater<int>()) mutates the remaining heap into output order before listString(const std::vector<int>&) formats it with std::stringstream; std::cout prints [9, 7, 5]. Visible allocation is the vector storage and formatting buffer; visible mutation is heap growth, root replacement, pop_back, swaps, and the final in-place sort.