概要

型パラメータを使った新しい二分ヒープ（最小ヒープ）パッケージ golang.org/x/exp/collection/heap を追加する提案です。既存の container/heap は使いにくいことで知られており、それに代わる API を目指しています。当初は標準ライブラリの container/heap/v2 として提案されていましたが、現在は x/exp に置く形に変わっています。

ステータス変更

(新規) → active
2026年10月8日、@aclements が proposal review group を代表して active 列に追加し、週次のレビュー会議で正式に議論されることになりました。背景として、2025年末に Go Collections ワーキンググループ（@jba, @adonovan, @griesemer, @mvdan, @rogpeppe, @khr, @ianlancetaylor）が発足し、Go 1.28 に向けた汎用コレクション型の提案群をまとめたことがあります。それらを束ねる umbrella issue #80590 が公開され、ヒープはその一部として扱われています。前日の10月7日には、提案者の @jba が最新の API（Clone メソッドの追加と x/exp/collection への移動）を公開し、実装 CL 846485 も投稿されました。審議に進む準備が整ったタイミングだと考えられます。

技術的背景

現状の問題点

container/heap には次の問題があります。

• ジェネリクスに対応していないので、要素を取り出すたびに型アサーションが必要です。
• Push(x any) の引数が any 型なので、値によってはアロケーション（メモリ確保）が発生します。
• ほぼ毎回スライスで済むのに、5つのメソッド（Len/Less/Swap/Push/Pop）を持つ型を利用者が毎回自分で書く必要があります。
• インターフェースのメソッドとパッケージ関数に同じ名前の Push/Pop があり、意味が違います。経験のある開発者でも混乱しやすい API です。
• 要素の優先度を後から変えたいときは、要素の構造体に index フィールドを持たせ、Swap の中で自分で更新し続ける必要があります。

提案された解決策

Heap[T] 型が内部ストレージを自分で管理し、比較関数を受け取ります。

• New(compare func(T, T) int): 通常のヒープを作ります。
• NewIndexed(compare, setIndex func(T, int)): 要素の位置が変わるたびに setIndex を呼び出し、位置を利用者に知らせるヒープを作ります。要素が取り除かれたときは -1 が渡されます。
• Min / TakeMin / ChangeMin: 最小要素の参照、取り出し、置き換えを行います。
• Insert / InsertAll(iter.Seq[T]): 要素を追加します。InsertAll はヒープをまとめて作り直すので O(n+k) で済みます。
• Init([]T): 渡したスライスからヒープを作ります。スライスの所有権はヒープに移ります。
• Changed(i) / Delete(i): 指定した位置の要素の位置を直す、または削除します。index 0 以外を指定できるのは NewIndexed で作ったヒープだけで、それ以外では panic します。
• All / Drain / Len / Clear / Clone: Drain はヒープを空にしながら要素を昇順に返すイテレータです。

これによって何ができるようになるか

• 優先度付きキュー: スケジューラ、離散イベントシミュレーション、Dijkstra 法などで、Insert と TakeMin を呼ぶだけで使えます。
• Top K: ChangeMin を使うと、ストリームから上位 K 件を O(K) のメモリで保持できます。最小要素を取り出してから挿入し直すより約2倍速いとされています。
• K-way マージ / 逐次ソート: Drain で昇順に少しずつ取り出せます。
• 優先度の動的変更: NewIndexed と Changed を使うと、対象の要素を O(log n) で正しい位置へ移動できます。

コード例

// Before: container/heap
type TaskHeap []*Task
func (h TaskHeap) Len() int           { return len(h) }
func (h TaskHeap) Less(i, j int) bool { return h[i].priority > h[j].priority }
func (h TaskHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
    h[i].index, h[j].index = i, j
}
func (h *TaskHeap) Push(x any) { t := x.(*Task); t.index = len(*h); *h = append(*h, t) }
func (h *TaskHeap) Pop() any {
    old := *h; n := len(old); t := old[n-1]; *h = old[:n-1]; return t
}
h := &TaskHeap{}
heap.Push(h, t)
t.priority++
heap.Fix(h, t.index)
top := heap.Pop(h).(*Task)
// After: golang.org/x/exp/collection/heap
type Task struct{ priority, index int }
func (t *Task) SetIndex(i int) { t.index = i }
h := heap.NewIndexed(
    func(a, b *Task) int { return cmp.Compare(b.priority, a.priority) }, // 優先度の高い順（最大ヒープ）
    (*Task).SetIndex,
)
h.Insert(t)
t.priority++
h.Changed(t.index)
top := h.TakeMin()

議論のハイライト

• 順序型（cmp.Ordered）専用の高速版は入れない: 専用版はヒープソートで約2倍速くなります。それでも @jba がエコシステムを調査したところ、本番コードでの利用はまれで、Grafana Pyroscope のベンチマークでもほとんど差がありませんでした。このため提案には含めていません。@jub0bs からは、将来専用版を追加する余地を残すために型名を HeapFunc にすべきという指摘がありました。@jba は、専用版を追加しないのであれば Func は余計だと答えています。
• 比較器を型パラメータにする案（Heap[T, C Comparer[T]]）は却下: 今の Go コンパイラは型ごとに特殊化したコード（monomorphization）を生成しないので、性能面の利点がありません。また、比較を関数リテラルで渡せなくなり書き方が冗長になるのも理由です。要素型に Compare メソッドを求める案に対しては、@ianlancetaylor が「メソッドより関数を使う方がよい」という立場を示しました。
• IndexedHeap を別の型に分ける案は見送り: 分ければ誤用をコンパイル時に検出できますが、ほとんどのメソッドが重複して API が複雑になります。panic で対応する方式を選びました。内部で map[*T]int を持つ案は、map の検索が入って遅くなるため却下されました。ハンドル方式（Boost.Heap 風）の案も、要素ごとにポインタが1つ余分に必要になるという懸念がありました。
• 名前の変更: Push/Pop/Fix/Remove をそれぞれ Insert/TakeMin/Changed/Delete に改めました。名前に "Min" を入れたのは、ドキュメントを見なくても最小ヒープだと分かるようにするためです。Top/TakeTop にすべきという意見もありました。
• 反対意見: VictoriaMetrics の開発者 @valyala は、スライスをその場でソートできなくなることなどを挙げ、実用上の価値に疑問を示しました。これに対し @ianlancetaylor は、v1 は Go 1 互換性保証によって残り続けること、そして多くの人にとっては新 API の方が分かりやすいことを述べています。