Heap Internals

平常用 PriorityQueue 就夠了，但理解堆積底層怎麼運作，能讓你看懂複雜度的由來、在面試被追問時答得出「為什麼建堆是 O(n)」，必要時也能手刻一個。堆積的精妙在於：它是一棵完全二元樹，卻能用一個陣列就表示，不需要任何指針。

陣列表示法

把完全二元樹按層由上而下、由左而右編號，放進陣列。以 0 為起點的索引關係：

            parent(i) = (i - 1) / 2
            left(i)   = 2 * i + 1
            right(i)  = 2 * i + 2

索引:   0     1     2     3     4     5
       [ 1 ]
        / \
     [ 3 ] [ 2 ]
      / \   /
   [ 7 ][6][ 5 ]

因為是完全二元樹，陣列中間不會有空洞，存取父子只靠算術、O(1)。

siftUp 與 siftDown

維持「堆性質」（每個父節點都不大於子節點，以 min-heap 為例）靠兩個操作：

• siftUp（上浮）：新元素加在陣列尾端，若比父節點小就與父交換，一路上浮到合適位置。用於插入。
• siftDown（下沉）：把某節點與較小的子節點比較並交換，一路下沉。用於取出堆頂（先把尾端搬到頂端再下沉）與建堆。

class MinHeap {
    private val a = ArrayList<Int>()

    fun offer(x: Int) {
        a.add(x)
        siftUp(a.size - 1)
    }

    fun poll(): Int {
        val top = a[0]
        val last = a.removeAt(a.size - 1)
        if (a.isNotEmpty()) {
            a[0] = last
            siftDown(0)
        }
        return top
    }

    private fun siftUp(i: Int) {
        var c = i
        while (c > 0) {
            val p = (c - 1) / 2
            if (a[c] >= a[p]) break
            a[c] = a[p].also { a[p] = a[c] }
            c = p
        }
    }

    private fun siftDown(i: Int) {
        var p = i
        val n = a.size
        while (true) {
            var smallest = p
            val l = 2 * p + 1
            val r = 2 * p + 2
            if (l < n && a[l] < a[smallest]) smallest = l
            if (r < n && a[r] < a[smallest]) smallest = r
            if (smallest == p) break
            a[p] = a[smallest].also { a[smallest] = a[p] }
            p = smallest
        }
    }
}

建堆為什麼是 O(n)

把任意陣列原地建成堆，做法是從最後一個非葉節點往前，對每個節點 siftDown。

直覺上像是 n 次 O(log n) = O(n log n)，但實際是 O(n)：siftDown 的成本與節點到底部的高度成正比，而堆裡絕大多數節點都在底層、高度很小。把各層的「節點數 × 高度」加總，級數收斂到 O(n)。

heapsort

堆排序分兩階段：

1. 建堆 O(n)：把陣列建成 max-heap。
2. 反覆取出 O(n log n)：把堆頂（最大值）與尾端交換，縮小堆範圍再 siftDown，重複 n 次。

整體 O(n log n)、原地、O(1) 額外空間，但不穩定。實務上因快取局部性不如快排而較少作為預設排序，但它的最壞情況保證 O(n log n)。

跨倉庫導讀

• 對應理論章節：樹、排序演算法