Top-K with a Heap - Swift DSA

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.

Swift DSA Implementation

basic.swift

func listString(_ values: [Int]) -> String { "[" + values.map(String.init).joined(separator: ", ") + "]" }
func heapInsert(_ heap: inout [Int], _ value: Int) {
    heap.append(value)
    var child = heap.count - 1
    while child > 0 {
        let parent = (child - 1) / 2
        if heap[parent] <= heap[child] { break }
        heap.swapAt(parent, child)
        child = parent
    }
}
func heapPop(_ heap: inout [Int]) -> Int {
    let smallest = heap[0]
    heap[0] = heap.removeLast()
    var parent = 0
    while true {
        let left = parent * 2 + 1
        let right = left + 1
        if left >= heap.count { break }
        var child = left
        if right < heap.count && heap[right] < heap[left] { child = right }
        if heap[parent] <= heap[child] { break }
        heap.swapAt(parent, child)
        parent = child
    }
    return smallest
}
var heap: [Int] = []
for value in [5, 1, 9, 3, 7, 2] { heapInsert(&heap, value); if heap.count > 3 { _ = heapPop(&heap) } }
print(listString(heap.sorted(by: >)))

Implementation notes

var heap: [Int] = [] is the mutable Swift array used as a min-heap for the current top values.
The loop processes [5, 1, 9, 3, 7, 2] in order and calls heapInsert(&heap, value) for every candidate.
The size bound is the literal 3: after each insert, if heap.count > 3 calls _ = heapPop(&heap) to discard the current minimum.
heapInsert and heapPop both take inout [Int], so they mutate the same heap array through append, removeLast, index comparisons, and swapAt.
This is a min-heap strategy for largest-three selection: the root is the smallest kept value, and overflow removes that cutoff.
The trace shows the heap after each value: [5], [1, 5], [1, 5, 9], then [3, 5, 9] after inserting 3 and popping 1.
Inserting 7 leaves [5, 7, 9]; inserting 2 is followed by a pop, so the heap remains [5, 7, 9].
The heap array is not already descending, so heap.sorted(by: >) creates the printed order [9, 7, 5].

Output

[9, 7, 5]