配列に詰めた木 — ヒープは添字で親子をたどる

CPython の Lib/heapq.py(3.14 ブランチ、2026-10-07 取得)の冒頭です。

Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for all k, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite.

木という語より先に arrays とあり、不変式も添字の計算 2*k+1 で書かれています。同じファイルの解説(François Pinard)は、0〜30 の番号を木の形に並べた図のあとでこう述べます。

In the tree above, each cell 'k' is topping '2k+1' and '2k+2'.

降順の7個を heapify に掛けて、親を (k-1)//2 で引いてみます(Python 3.14.6 / macOS arm64、2026-10-07)。

[3, 8, 4, 9, 15, 20, 11]
k=1 値= 8  親 k=0 値= 3  親<=子: True
k=2 値= 4  親 k=0 値= 3  親<=子: True
k=3 値= 9  親 k=1 値= 8  親<=子: True
k=4 値=15  親 k=1 値= 8  親<=子: True
k=5 値=20  親 k=2 値= 4  親<=子: True
k=6 値=11  親 k=2 値= 4  親<=子: True

入力 [20, 15, 11, 9, 8, 4, 3] は [3, 8, 4, 9, 15, 20, 11] になりました。整列はしていませんが、どの親も子以下です。

同じ「隙間の無い木を配列に詰める」形を、分岐4で使っている実物があります。Go ランタイムの src/runtime/time.go です(master、2026-10-07 取得)。

const timerHeapN = 4

		p := int(uint(i-1) / timerHeapN) // parent

		leftChild := i*timerHeapN + 1

親は (i-1)/4、最初の子は i*4+1 で、2 が 4 に変わっただけです。この値は master・go1.25・go1.24・go1.23 で 4 です。go1.22 は定数ではなく (i - 1) / 4 の直書きで、// The heap is 4-ary. See siftupTimer and siftdownTimer. とコメントされています。

積み上げの費用も、ソースのコメントに書かれています。

// initHeap reestablishes the heap order in the slice ts.heap. // It takes O(n) time for n=len(ts.heap), not the O(n log n) of n repeated add operations.

分岐を増やすと何が起きるかは、添字の計算から出せます。10万件の末尾の深さは、二分で16段、4分で9段です。代わりに siftDown は、1段ごとに最大4つの子と比べます。段数を減らし、1段の仕事を増やす交換です。第11期『木を低くすると、読む回数が減る』で見た、扇出しと段数の関係と同じ形です。

ただし、なぜ4なのかはソースに書かれていません。 この「交換」という説明は教材側の解釈で、Go のコメントの主張ではありません。