[インデックス 17041] ファイルの概要

このコミットは、Go言語の標準ライブラリであるcontainer/heapパッケージに対する機能追加とドキュメントの改善を目的としています。具体的には、ヒープ内の特定要素の値が変更された際にヒープのプロパティを再確立するためのFix関数が追加され、またヒープの最小要素が常にインデックス0に位置することが明示的にドキュメント化されました。

コミット

commit dd6f49ddca0f54767d5cc26b5627f025f63cbcc3
Author: Pieter Droogendijk <pieter@binky.org.uk>
Date:   Mon Aug 5 15:45:39 2013 -0700

    container/heap: add Fix and document the min is element 0.
    
    Fixes #5372.
    Fixes #5577.
    
    R=gri, rsc, bradfitz, r
    CC=golang-dev
    https://golang.org/cl/12265043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/dd6f49ddca0f54767d5cc26b5627f025f63cbcc3

元コミット内容

container/heap: add Fix and document the min is element 0.

Fixes #5372.
Fixes #5577.

R=gri, rsc, bradfitz, r
CC=golang-dev
https://golang.org/cl/12265043

変更の背景

このコミットは、Goのcontainer/heapパッケージの利便性と堅牢性を向上させるために行われました。主な背景は以下の2点です。

ヒープ要素の更新効率化: 既存のcontainer/heapパッケージでは、ヒープ内の特定要素の値が変更された場合、その要素を一度ヒープから削除し（Remove）、新しい値で再度追加する（Push）という手順が必要でした。これは、特に頻繁に要素の値が更新されるようなシナリオ（例: ダイクストラ法における距離の更新）において非効率的でした。Fix関数の導入により、この操作がより効率的に行えるようになります。
ドキュメントの明確化: ヒープの最小要素が常にインデックス0に位置するという重要なプロパティが、明示的にドキュメントに記載されていませんでした。これにより、ユーザーがヒープの最小値にアクセスする際に、その場所を推測する必要がありました。ドキュメントに明記することで、APIの使いやすさと理解度が向上します。

コミットメッセージに記載されているFixes #5372とFixes #5577は、これらの改善が特定の課題やバグ報告に対応していることを示唆していますが、公開されているGoのIssue Trackerでは直接的な関連が見つかりませんでした。これは、内部的なトラッカーの番号であるか、あるいは関連する議論が別の場所で行われていた可能性を示唆しています。

前提知識の解説

ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、ヒーププロパティと呼ばれる特定の順序付けプロパティを満たします。ヒープには主に以下の2種類があります。

最小ヒープ (Min-Heap): 各ノードの値が、その子ノードの値よりも小さいか等しい。結果として、ルートノード（最上位のノード）がヒープ全体の最小値になります。
最大ヒープ (Max-Heap): 各ノードの値が、その子ノードの値よりも大きいか等しい。結果として、ルートノードがヒープ全体の最大値になります。

Goのcontainer/heapパッケージは最小ヒープを実装しており、優先度キューの実装によく利用されます。ヒープは通常、配列（またはスライス）で表現され、ツリー構造はインデックスの計算によってシミュレートされます。

親ノードのインデックスが i の場合、左の子ノードのインデックスは 2*i + 1、右の子ノードのインデックスは 2*i + 2 です。
子ノードのインデックスが j の場合、親ノードのインデックスは (j - 1) / 2 です（整数除算）。

ヒープ操作の基本

Init(h Interface): スライスをヒーププロパティを満たすように再編成します。O(n)の時間計算量。
Push(h Interface, x interface{}): 要素 x をヒープに追加し、ヒーププロパティを維持します。O(log n)の時間計算量。
Pop(h Interface) interface{}: ヒープの最小要素（ルート）を削除し、それを返します。ヒーププロパティを維持します。O(log n)の時間計算量。
Remove(h Interface, i int) interface{}: インデックス i の要素をヒープから削除し、それを返します。ヒーププロパティを維持します。O(log n)の時間計算量。

`up`と`down`操作

ヒーププロパティを維持するために、以下の2つの補助関数が内部的に使用されます。

up(h Interface, j int): インデックス j の要素がその親よりも小さい場合に、要素をヒープの上方へ移動させ、ヒーププロパティを再確立します。これは、新しい要素が追加された後や、要素の値が減少した場合に必要になります。
down(h Interface, i, n int): インデックス i の要素がその子よりも大きい場合に、要素をヒープの下方へ移動させ、ヒーププロパティを再確立します。これは、ルート要素が削除された後や、要素の値が増加した場合に必要になります。

技術的詳細

このコミットの技術的な変更点は以下の通りです。

Fix関数の追加:
- Fix(h Interface, i int)関数がcontainer/heapパッケージに追加されました。
- この関数は、ヒープ内のインデックスiにある要素の値が変更された後に呼び出され、ヒーププロパティを再確立します。
- 内部的には、down操作とup操作を順に呼び出すことで、要素が新しい値に基づいて適切な位置に移動するようにします。
- Remove(h, i)の後に新しい値をPushするよりも効率的です。Removeは要素を削除した後にヒープの再構築を行い、Pushは新しい要素を追加した後に再度ヒープの再構築を行うため、2回のヒープ操作が必要になります。Fixは1回の操作でこれを実現します。
- 時間計算量はO(log n)です。
ドキュメントの改善:
- src/pkg/container/heap/heap.goのコメントに、ヒープの最小要素がインデックス0に位置することが明示的に追記されました。
```
// The minimum element in the tree is the root, at index 0.
```
- Pop関数のコメントが「Same as Remove(h, 0).」から「It is equivalent to Remove(h, 0).」に変更され、より正確な表現になりました。
テストケースの追加と修正:
- src/pkg/container/heap/example_intheap_test.goのExample_intHeapに、ヒープの最小値（インデックス0の要素）を出力する行が追加され、ドキュメントの変更と整合性が取られました。
- src/pkg/container/heap/heap_test.goにTestFixという新しいテスト関数が追加されました。このテストは、Fix関数の正しい動作を検証するために、ヒープの要素をランダムに更新し、その都度Fixを呼び出してヒーププロパティが維持されていることを確認します。

コアとなるコードの変更箇所

`src/pkg/container/heap/heap.go`

--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -6,6 +6,8 @@
 // heap.Interface. A heap is a tree with the property that each node is the
 // minimum-valued node in its subtree.
 //
+// The minimum element in the tree is the root, at index 0.
+//
 // A heap is a common way to implement a priority queue. To build a priority
 // queue, implement the Heap interface with the (negative) priority as the
 // ordering for the Less method, so Push adds items while Pop removes the
@@ -54,7 +56,7 @@ func Push(h Interface, x interface{}) {
 
 // Pop removes the minimum element (according to Less) from the heap
 // and returns it. The complexity is O(log(n)) where n = h.Len().
-// Same as Remove(h, 0).
+// It is equivalent to Remove(h, 0).
 //
 func Pop(h Interface) interface{} {
  	n := h.Len() - 1
@@ -76,6 +78,15 @@ func Remove(h Interface, i int) interface{} {
  	return h.Pop()
 }
 
+// Fix reestablishes the heap ordering after the element at index i has changed its value.
+// Changing the value of the element at index i and then calling Fix is equivalent to,
+// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
+// The complexity is O(log(n)) where n = h.Len().
+func Fix(h Interface, i int) {
+	down(h, i, h.Len())
+	up(h, i)
+}
+
 func up(h Interface, j int) {
  	for {
  	\ti := (j - 1) / 2 // parent

`src/pkg/container/heap/example_intheap_test.go`

--- a/src/pkg/container/heap/example_intheap_test.go
+++ b/src/pkg/container/heap/example_intheap_test.go
@@ -31,13 +31,17 @@ func (h *IntHeap) Pop() interface{} {
  	return x
 }
 
-// This example inserts several ints into an IntHeap and removes them in order of priority.
+// This example inserts several ints into an IntHeap, checks the minimum,
+// and removes them in order of priority.
 func Example_intHeap() {
  	h := &IntHeap{2, 1, 5}
  	heap.Init(h)
  	heap.Push(h, 3)
+\tfmt.Printf("minimum: %d\n", (*h)[0])
  	for h.Len() > 0 {
  	\tfmt.Printf("%d ", heap.Pop(h))
  	}
-\t// Output: 1 2 3 5
+\t// Output:
+\t// minimum: 1
+\t// 1 2 3 5
 }

`src/pkg/container/heap/heap_test.go`

--- a/src/pkg/container/heap/heap_test.go
+++ b/src/pkg/container/heap/heap_test.go
@@ -5,6 +5,7 @@
 package heap
 
 import (
+\t"math/rand"
  	"testing"
 )
 
@@ -182,3 +183,31 @@ func BenchmarkDup(b *testing.B) {
  	\t}
  	}
 }
+\n+func TestFix(t *testing.T) {\n+\th := new(myHeap)\n+\th.verify(t, 0)\n+\n+\tfor i := 200; i > 0; i -= 10 {\n+\t\tPush(h, i)\n+\t}\n+\th.verify(t, 0)\n+\n+\tif (*h)[0] != 10 {\n+\t\tt.Fatalf("Expected head to be 10, was %d", (*h)[0])\n+\t}\n+\t(*h)[0] = 210\n+\tFix(h, 0)\n+\th.verify(t, 0)\n+\n+\tfor i := 100; i > 0; i-- {\n+\t\telem := rand.Intn(h.Len())\n+\t\tif i&1 == 0 {\n+\t\t\t(*h)[elem] *= 2\n+\t\t} else {\n+\t\t\t(*h)[elem] /= 2\n+\t\t}\n+\t\tFix(h, elem)\n+\t\th.verify(t, 0)\n+\t}\n+}\n```

## コアとなるコードの解説

### `Fix`関数の実装

`Fix`関数は、ヒープの特定の要素が変更されたときにヒーププロパティを再確立するための重要な関数です。

```go
func Fix(h Interface, i int) {
	down(h, i, h.Len())
	up(h, i)
}

この関数は、以下のロジックで動作します。

down(h, i, h.Len()): まず、インデックスiの要素に対してdown操作を実行します。これは、h[i]の値が増加した場合（つまり、その子が新しい親になるべき場合）に、要素をヒープの下方へ移動させることでヒーププロパティを回復させます。
up(h, i): 次に、インデックスiの要素に対してup操作を実行します。これは、h[i]の値が減少した場合（つまり、その親が新しい子になるべき場合）に、要素をヒープの上方へ移動させることでヒーププロパティを回復させます。

なぜ両方の操作が必要なのでしょうか？要素の値が変更された場合、その新しい値が元の位置でヒーププロパティを壊す可能性があります。

もし新しい値が元の値より小さくなった場合、その要素はヒープのより上層に移動する必要があるかもしれません。この場合、up操作が適切です。
もし新しい値が元の値より大きくなった場合、その要素はヒープのより下層に移動する必要があるかもしれません。この場合、down操作が適切です。

Fix関数は、値の増減どちらのケースにも対応できるように、両方の操作を順に実行します。down操作は要素を可能な限り下方に移動させ、その後up操作が要素を適切な位置まで上方に移動させます。これにより、ヒーププロパティが確実に再確立されます。

ドキュメントの明確化

src/pkg/container/heap/heap.goの冒頭に以下のコメントが追加されました。

// The minimum element in the tree is the root, at index 0.

これは、Goのcontainer/heapパッケージが最小ヒープとして機能し、その最小値が常にスライスの最初の要素（インデックス0）に格納されていることを明示的に示しています。これにより、ユーザーはヒープの最小値にアクセスするためにh[0]を使用できることが明確になります。

また、Pop関数のコメントが「Same as Remove(h, 0).」から「It is equivalent to Remove(h, 0).」に変更されました。これは、PopがRemove(h, 0)と全く同じ実装ではないが、結果として同じ動作をすることをより正確に表現しています。

テストケースの追加

TestFix関数は、Fix関数の堅牢性を検証するために設計されています。

初期化されたヒープに複数の要素を追加します。
ヒープのルート要素（インデックス0）の値を意図的に変更し、Fix(h, 0)を呼び出してヒーププロパティが回復するかを確認します。
さらに、ヒープ内のランダムな要素の値をランダムに増減させ、その都度Fixを呼び出し、h.verify(t, 0)（ヒーププロパティの検証関数）を使ってヒープが常に有効な状態であることを確認します。

このテストは、Fix関数が様々なシナリオで正しく機能することを保証し、ヒープの整合性を維持する上で非常に重要です。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のcontainer/heapパッケージのソースコード
ヒープデータ構造に関する一般的なアルゴリズムの知識

comemo