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.

Perl DSA Implementation

basic.pl

use strict;
use warnings;
sub list_string { return "[" . join(", ", @_) . "]"; }
sub heap_insert {
    my ($heap, $value) = @_;
    push @$heap, $value;
    my $child = scalar(@$heap) - 1;
    while ($child > 0) {
        my $parent = int(($child - 1) / 2);
        last if $heap->[$parent] <= $heap->[$child];
        ($heap->[$parent], $heap->[$child]) = ($heap->[$child], $heap->[$parent]);
        $child = $parent;
    }
}
sub heap_pop {
    my ($heap) = @_;
    my $smallest = $heap->[0];
    $heap->[0] = pop @$heap;
    my $parent = 0;
    while (1) {
        my $left = $parent * 2 + 1; my $right = $left + 1;
        last if $left >= scalar @$heap;
        my $child = $left;
        $child = $right if $right < scalar @$heap && $heap->[$right] < $heap->[$left];
        last if $heap->[$parent] <= $heap->[$child];
        ($heap->[$parent], $heap->[$child]) = ($heap->[$child], $heap->[$parent]);
        $parent = $child;
    }
    return $smallest;
}
my @heap;
for my $value (5, 1, 9, 3, 7, 2) { heap_insert(\@heap, $value); heap_pop(\@heap) if scalar(@heap) > 3; }
@heap = sort { $b <=> $a } @heap;
print list_string(@heap) . "\n";

Implementation notes

my @heap starts as an empty Perl array used as a bounded min-heap.
The pinned candidates are scanned in this order: 5, 1, 9, 3, 7, 2.
There is no separate $k variable in the source; the size limit is the literal check scalar(@heap) > 3.
Each candidate calls heap_insert(\@heap, $value), passing an array reference so the helper mutates the original heap.
heap_insert appends with push @$heap, $value, then sifts up with zero-based parent math: int(($child - 1) / 2).
The heap is a min-heap because sift-up stops when $heap->[$parent] <= $heap->[$child].
Swaps use Perl list assignment: ($heap->[$parent], $heap->[$child]) = ($heap->[$child], $heap->[$parent]).
If the heap grows past three items, heap_pop(\@heap) removes the smallest root value and sifts the replacement down.
heap_pop uses pop @$heap to move the last array value to the root, then uses left = parent * 2 + 1 and right = left + 1 to choose the smaller child.

Top-k replay

consider 5: [5]
consider 1: [1, 5]
consider 9: [1, 5, 9]
consider 3: insert, then pop 1  -> [3, 5, 9]
consider 7: insert, then pop 3  -> [5, 7, 9]
consider 2: insert, then pop 2  -> [5, 7, 9]

Before printing, @heap = sort { $b <=> $a } @heap sorts the surviving values from high to low.
list_string(@heap) joins the final array with ", ", and print ... . "\n" outputs [9, 7, 5].

Output

[9, 7, 5]