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.

Java DSA Implementation

Basic.java

import java.util.*;
class Basic {
    static String listString(List<Integer> values) { return values.toString(); }
    static void heapInsert(List<Integer> heap, int value) {
        heap.add(value);
        int child = heap.size() - 1;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (heap.get(parent) <= heap.get(child)) break;
            Collections.swap(heap, parent, child);
            child = parent;
        }
    }
    static int heapPop(List<Integer> heap) {
        int smallest = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1));
        int parent = 0;
        while (true) {
            int left = parent * 2 + 1;
            int right = left + 1;
            if (left >= heap.size()) break;
            int child = left;
            if (right < heap.size() && heap.get(right) < heap.get(left)) child = right;
            if (heap.get(parent) <= heap.get(child)) break;
            Collections.swap(heap, parent, child);
            parent = child;
        }
        return smallest;
    }
    public static void main(String[] args) { List<Integer> heap = new ArrayList<>(); for (int value : new int[] {5, 1, 9, 3, 7, 2}) { heapInsert(heap, value); if (heap.size() > 3) heapPop(heap); } heap.sort(Collections.reverseOrder()); System.out.println(listString(heap)); }
}

Output

[9, 7, 5]

Implementation notes

This Java version uses the lesson's manual min-heap helpers over a List<Integer> backed by an ArrayList, not PriorityQueue. Values from the input int[] are boxed through Integer.valueOf, so these small fixture values may be cached Integer instances when inserted.
heapInsert appends to the list and sifts upward with parent index (child - 1) / 2; heapPop removes the current minimum root and sifts the replacement down with child indexes parent * 2 + 1 and right = left + 1. The heap comparisons unbox Integer values for primitive <= and < checks.
The top-k bound is maintained by if (heap.size() > 3) heapPop(heap) after each insert. Because the heap is a min-heap, popping discards the current cutoff and keeps the largest three values seen so far.
The replay-visible heap states progress through [1, 5, 9], [3, 5, 9], and [5, 7, 9]. Before printing, heap.sort(Collections.reverseOrder()) mutates that same list into [9, 7, 5].
Allocation is mainly the ArrayList storage and any uncached boxed integers; Collections.reverseOrder() supplies the comparator used for the final in-place sort.