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.

PHP DSA Implementation

basic.php

<?php
function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }
function heap_insert(array &$heap, int $value): void {
    $heap[] = $value;
    $child = count($heap) - 1;
    while ($child > 0) {
        $parent = intdiv($child - 1, 2);
        if ($heap[$parent] <= $heap[$child]) break;
        [$heap[$parent], $heap[$child]] = [$heap[$child], $heap[$parent]];
        $child = $parent;
    }
}
function heap_pop(array &$heap): int {
    $smallest = $heap[0];
    $heap[0] = array_pop($heap);
    $parent = 0;
    while (true) {
        $left = $parent * 2 + 1; $right = $left + 1;
        if ($left >= count($heap)) break;
        $child = $left;
        if ($right < count($heap) && $heap[$right] < $heap[$left]) $child = $right;
        if ($heap[$parent] <= $heap[$child]) break;
        [$heap[$parent], $heap[$child]] = [$heap[$child], $heap[$parent]];
        $parent = $child;
    }
    return $smallest;
}
$heap = [];
foreach ([5, 1, 9, 3, 7, 2] as $value) { heap_insert($heap, $value); if (count($heap) > 3) heap_pop($heap); }
rsort($heap);
echo list_string($heap) . PHP_EOL;
?>

Implementation notes

The input values are the PHP array literal [5, 1, 9, 3, 7, 2].
$heap = [] starts empty, and k is the literal size guard count($heap) > 3.
heap_insert(array &$heap, int $value): void and heap_pop(array &$heap): int both mutate the same heap array by reference.
The helpers use min-heap order: parent values must be <= child values, and sift-down chooses the smaller child when both children exist.
Parent indexes use intdiv($child - 1, 2); child indexes use $left = $parent * 2 + 1 and $right = $left + 1.
Swaps use PHP array destructuring assignment between heap slots.
Each input is inserted first; when the heap grows to four items, heap_pop($heap) removes the current smallest cutoff.
The trace keeps [5], then [1, 5], then [1, 5, 9].
Considering 3 inserts then pops 1, leaving [3, 5, 9]; considering 7 inserts then pops 3, leaving [5, 7, 9].
Considering 2 inserts then pops 2, so the top-k heap remains [5, 7, 9].
rsort($heap) mutates the heap array into descending output order before printing.
echo list_string($heap) . PHP_EOL prints [9, 7, 5].

Output

[9, 7, 5]