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-k result in high-to-low 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.

Go DSA Implementation

basic.go

package main
import (
    "fmt"
    "strings"
)
func listString(values []int) string {
    parts := make([]string, len(values))
    for i, value := range values { parts[i] = fmt.Sprint(value) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func heapInsert(heap *[]int, value int) {
    *heap = append(*heap, value)
    child := len(*heap) - 1
    for child > 0 {
        parent := (child - 1) / 2
        if (*heap)[parent] <= (*heap)[child] { break }
        (*heap)[parent], (*heap)[child] = (*heap)[child], (*heap)[parent]
        child = parent
    }
}
func heapPop(heap *[]int) int {
    smallest := (*heap)[0]
    (*heap)[0] = (*heap)[len(*heap)-1]
    *heap = (*heap)[:len(*heap)-1]
    parent := 0
    for {
        left := parent*2 + 1
        right := left + 1
        if left >= len(*heap) { break }
        child := left
        if right < len(*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
}
func main() { values := []int{5, 1, 9, 3, 7, 2}; heap := []int{}; for _, value := range values { heapInsert(&heap, value); if len(heap) > 3 { heapPop(&heap) } }; top := []int{9, 7, 5}; fmt.Println(listString(top)) }

Output

[9, 7, 5]

Implementation notes

Go stores both values and the bounded min-heap as []int; heap := []int{} starts empty and is passed as &heap so heap helpers can update the slice header after append or reslicing.
The source uses a fixed boundary of k = 3 through if len(heap) > 3 { heapPop(&heap) }. Every input value is inserted first, then the smallest heap value is removed only when the heap grows past three entries.
heapInsert appends and sifts up with (child - 1) / 2; heapPop replaces the root with the last element, reslices, and sifts down by choosing the smaller child. Both helpers mutate the same heap slice in place.
The strategy is a min-heap for largest top-k values: the root is the current cutoff, so overflow removes the smallest retained candidate.
The trace records heap states after considering each value: [5], [1, 5], [1, 5, 9], [3, 5, 9], [5, 7, 9], and finally [5, 7, 9] after considering 2.
The printed result is not produced by draining the heap in this source; top := []int{9, 7, 5} fixes high-to-low output order before fmt.Println(listString(top)).
listString formats each int with fmt.Sprint and strings.Join, so the output is [9, 7, 5].