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

このコミットは、Go言語の標準ライブラリである container/heap パッケージの example_pq_test.go ファイル内のサンプルコードを更新するものです。具体的には、ヒープの不変条件を確立するための heap.Init の適切な使用方法と、要素のプロパティが変更された後にヒープを更新するための heap.Fix の使用方法を反映しています。

コミット

container/heap パッケージのサンプルコードを更新し、非空のヒープに対してヒープの不変条件を確立するために Init を使用し、要素のプロパティが変更された後にヒープを更新するために Fix を使用するように修正しました。これは、古いコードが不要な場所で Init を使用し、Fix が追加された後にサンプルが書かれたため Fix を使用していなかった問題を解決します。

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

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

元コミット内容

container/heap: update example code

- use Init to establish heap invariant on
  a non-empty heap
- use Fix to update heap after an element's
  properties have been changed

(The old code used Init where it wasn't needed,
 and didn't use Fix because Fix was added after
 the example was written.)

LGTM=bradfitz
R=adonovan, bradfitz
CC=golang-codereviews
https://golang.org/cl/94520043

変更の背景

このコミットの背景には、container/heap パッケージの進化と、それに伴うサンプルコードの陳腐化があります。

元々、container/heap パッケージのサンプルコードは、heap.Fix 関数が導入される前に書かれていました。heap.Fix は、ヒープ内の特定要素の優先度（または値）が変更された際に、ヒープの不変条件を効率的に再確立するための重要な関数です。しかし、この関数が存在しなかったため、古いサンプルコードでは要素の更新を行う際に、一度ヒープから要素を削除し（heap.Remove）、そのプロパティを変更した後、再度ヒープに挿入する（heap.Push）という非効率な方法が取られていました。

また、heap.Init 関数についても、その使用法に関する誤解や不適切な適用が見られました。heap.Init は、既存の要素のコレクションからヒープを構築する際に、ヒープの不変条件を確立するために使用されます。しかし、古いサンプルコードでは、既に空のヒープに対して Init を呼び出すなど、不要な場所で使用されているケースがありました。

このコミットは、これらの問題を修正し、container/heap パッケージの最新の機能と推奨される使用パターンを反映させることを目的としています。これにより、サンプルコードがより効率的で、かつパッケージの意図する正しい使い方を示すものとなります。

前提知識の解説

このコミットを理解するためには、以下の概念とGo言語の container/heap パッケージに関する知識が必要です。

1. ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、特定のヒーププロパティ（不変条件）を満たします。主な種類は以下の通りです。

最小ヒープ (Min-Heap): 親ノードの値がその子ノードの値よりも常に小さいか等しい。したがって、根（ルート）ノードがヒープ内の最小値を持つ。
最大ヒープ (Max-Heap): 親ノードの値がその子ノードの値よりも常に大きいか等しい。したがって、根ノードがヒープ内の最大値を持つ。

Goの container/heap パッケージは、最小ヒープとして実装されており、優先度キューなどの実装に利用されます。ヒープは通常、配列で表現され、特定のインデックス計算によって親子関係が表現されます。

2. 優先度キュー (Priority Queue)

優先度キューは、各要素に「優先度」が割り当てられた抽象データ型です。通常のキューとは異なり、要素は追加された順序ではなく、その優先度に基づいて取り出されます。最も優先度の高い要素が最初に取り出されます。ヒープは、優先度キューを効率的に実装するための一般的なデータ構造です。

3. Go言語 `container/heap` パッケージ

container/heap パッケージは、任意の型をヒープとして扱うための汎用的なインターフェースと関数を提供します。このパッケージを使用するには、sort.Interface を実装し、さらに Push と Pop メソッドを追加で実装する必要があります。

主要な関数は以下の通りです。

heap.Init(h Interface): h がヒープの不変条件を満たすように初期化します。これは、既存の要素のコレクション（例えば、スライス）からヒープを構築する際に使用されます。要素が既にスライスに存在する場合、この関数を呼び出すことで、そのスライスがヒープのプロパティを満たすように再配置されます。
heap.Push(h Interface, x interface{}): 要素 x をヒープ h に追加し、ヒープの不変条件を維持します。
heap.Pop(h Interface) interface{}: ヒープ h から最小（または最大、実装による）要素を削除して返します。ヒープの不変条件は維持されます。
heap.Remove(h Interface, i int) interface{}: ヒープ h からインデックス i の要素を削除して返します。ヒープの不変条件は維持されます。
heap.Fix(h Interface, i int): インデックス i の要素の優先度（または値）が変更された後、ヒープの不変条件を再確立します。この関数は、要素の値を変更した後に呼び出す必要があります。Remove と Push を組み合わせるよりも効率的です。

4. ヒープの不変条件 (Heap Invariant)

ヒープの不変条件とは、ヒープが常に満たすべきプロパティのことです。最小ヒープの場合、これは「親ノードの値は常にその子ノードの値以下である」という条件です。ヒープに対する操作（追加、削除、更新）が行われた後も、この不変条件が維持されるように、内部的に要素の再配置（ヒープ化操作、heapify）が行われます。

技術的詳細

このコミットは、container/heap パッケージの example_pq_test.go 内の PriorityQueue のサンプル実装における2つの主要な改善点に焦点を当てています。

1. `heap.Init` の適切な使用

変更前は、Example_priorityQueue 関数内で、空の PriorityQueue を作成した直後に heap.Init(pq) を呼び出していました。

// 変更前
pq := &PriorityQueue{}
heap.Init(pq) // ここでInitを呼び出している
// ... その後、要素をPush

heap.Init は、既に要素が含まれているスライスをヒープとして初期化するために使用されます。空のヒープに対して Init を呼び出すことは、技術的には問題ありませんが、不要な操作であり、コードの意図を不明瞭にする可能性があります。

変更後では、まず make を使用して、初期アイテムの数に基づいて PriorityQueue スライスを初期化し、そこに直接アイテムを格納しています。

// 変更後
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
    pq[i] = &Item{
        value:    value,
        priority: priority,
        index:    i, // indexもここで設定
    }
    i++
}
heap.Init(&pq) // 全てのアイテムがスライスに格納された後にInitを呼び出す

この変更により、pq スライスが初期アイテムで満たされた後に heap.Init(&pq) が呼び出され、スライス全体が正しくヒープの不変条件を満たすように初期化されます。これは heap.Init の本来の意図に沿った正しい使用方法です。

2. `heap.Fix` の導入による要素更新の効率化

変更前は、PriorityQueue の update メソッドで、既存の要素の優先度を変更する際に、一度ヒープからその要素を削除し（heap.Remove）、プロパティを変更した後、再度ヒープに挿入する（heap.Push）という手順を踏んでいました。

// 変更前 - updateメソッド
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    heap.Remove(pq, item.index) // 一度削除
    item.value = value
    item.priority = priority
    heap.Push(pq, item) // 再度追加
}

この Remove と Push の組み合わせは、要素の更新を行うための有効な手段ではありますが、非効率です。特に、要素のインデックスが分かっている場合、heap.Fix を使用する方がはるかに効率的です。heap.Fix は、指定されたインデックスの要素の値が変更されたことをヒープに通知し、その要素を適切な位置に移動させることで、ヒープの不変条件を再確立します。これにより、ヒープ全体の再構築を避けることができます。

変更後では、この非効率な Remove と Push の組み合わせを heap.Fix に置き換えています。

// 変更後 - updateメソッド
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index) // Fixを呼び出す
}

この変更により、update 操作のパフォーマンスが向上し、コードもより簡潔で意図が明確になります。heap.Fix は、要素のインデックスが既知である場合に、ヒープ内の要素の優先度を更新する際の推奨される方法です。

これらの変更は、container/heap パッケージの利用者が、より効率的で正しいヒープ操作のパターンを理解し、適用できるようにするための重要な改善です。

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

src/pkg/container/heap/example_pq_test.go ファイルにおける変更箇所は以下の通りです。

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -52,13 +52,12 @@ func (pq *PriorityQueue) Pop() interface{} {
 
 // update modifies the priority and value of an Item in the queue.
 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
-	heap.Remove(pq, item.index)
 	item.value = value
 	item.priority = priority
-	heap.Push(pq, item)
+	heap.Fix(pq, item.index)
 }
 
-// This example inserts some items into a PriorityQueue, manipulates an item,
+// This example creates a PriorityQueue with some items, adds and manipulates an item,
 // and then removes the items in priority order.
 func Example_priorityQueue() {
 	// Some items and their priorities.
@@ -66,28 +65,31 @@ func Example_priorityQueue() {
 		"banana": 3, "apple": 2, "pear": 4,
 	}
 
-	// Create a priority queue and put the items in it.
-	pq := &PriorityQueue{}
-	heap.Init(pq)
+	// Create a priority queue, put the items in it, and
+	// establish the priority queue (heap) invariants.
+	pq := make(PriorityQueue, len(items))
+	i := 0
 	for value, priority := range items {
-		item := &Item{
+		pq[i] = &Item{
 			value:    value,
 			priority: priority,
+			index:    i,
 		}
-		heap.Push(pq, item)
+		i++
 	}
+	heap.Init(&pq)
 
 	// Insert a new item and then modify its priority.
 	item := &Item{
 		value:    "orange",
 		priority: 1,
 	}
-	heap.Push(pq, item)
+	heap.Push(&pq, item)
 	pq.update(item, item.value, 5)
 
 	// Take the items out; they arrive in decreasing priority order.
 	for pq.Len() > 0 {
-		item := heap.Pop(pq).(*Item)
+		item := heap.Pop(&pq).(*Item)
 		fmt.Printf("%.2d:%s ", item.priority, item.value)
 	}
 	// Output:

コアとなるコードの解説

`update` メソッドの変更

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -52,13 +52,12 @@ func (pq *PriorityQueue) Pop() interface{} {
 
 // update modifies the priority and value of an Item in the queue.
 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
-	heap.Remove(pq, item.index)
 	item.value = value
 	item.priority = priority
-	heap.Push(pq, item)
+	heap.Fix(pq, item.index)
 }

- heap.Remove(pq, item.index): 変更前は、アイテムの優先度を更新するために、まずヒープからそのアイテムを削除していました。
- heap.Push(pq, item): 削除後、アイテムのプロパティを変更し、再度ヒープにプッシュしていました。この Remove と Push の組み合わせは、アイテムの更新には機能しますが、非効率です。
+ heap.Fix(pq, item.index): 変更後では、heap.Fix 関数が導入されました。アイテムの value と priority を更新した後、heap.Fix を呼び出すことで、指定された item.index の要素がヒープの不変条件を維持するように、効率的にヒープ内で再配置されます。これにより、不要な削除と再挿入のオーバーヘッドがなくなります。

`Example_priorityQueue` 関数の変更

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -66,28 +65,31 @@ func Example_priorityQueue() {
 		"banana": 3, "apple": 2, "pear": 4,
 	}
 
-	// Create a priority queue and put the items in it.
-	pq := &PriorityQueue{}
-	heap.Init(pq)
+	// Create a priority queue, put the items in it, and
+	// establish the priority queue (heap) invariants.
+	pq := make(PriorityQueue, len(items))
+	i := 0
 	for value, priority := range items {
-		item := &Item{
+		pq[i] = &Item{
 			value:    value,
 			priority: priority,
+			index:    i,
 		}
-		heap.Push(pq, item)
+		i++
 	}
+	heap.Init(&pq)
 
 	// Insert a new item and then modify its priority.
 	item := &Item{
 		value:    "orange",
 		priority: 1,
 	}
-	heap.Push(pq, item)
+	heap.Push(&pq, item)
 	pq.update(item, item.value, 5)
 
 	// Take the items out; they arrive in decreasing priority order.
 	for pq.Len() > 0 {
-		item := heap.Pop(pq).(*Item)
+		item := heap.Pop(&pq).(*Item)
 		fmt.Printf("%.2d:%s ", item.priority, item.value)
 	}
 	// Output:

ヒープの初期化方法の変更:
- 変更前: pq := &PriorityQueue{} で空のヒープを作成し、すぐに heap.Init(pq) を呼び出していました。これは、heap.Init が既存の要素を持つスライスをヒープ化するために設計されているため、不要な呼び出しでした。
- 変更後: pq := make(PriorityQueue, len(items)) を使用して、初期アイテムの数に合わせてスライスを事前に確保しています。その後、ループ内で直接 pq[i] = &Item{...} のようにアイテムをスライスに格納し、item.index も設定しています。全てのアイテムがスライスに格納された後、heap.Init(&pq) を呼び出すことで、スライス全体が一度にヒープの不変条件を満たすように初期化されます。これは、既存のコレクションからヒープを構築する際の正しいパターンです。
heap.Push と heap.Pop の引数変更:
- 変更前は heap.Push(pq, item) や heap.Pop(pq) のように、PriorityQueue のポインタではない値を渡していました。
- 変更後: heap.Push(&pq, item) や heap.Pop(&pq) のように、PriorityQueue のポインタを渡すように修正されています。container/heap のインターフェースはポインタレシーバを持つメソッドを期待するため、これは正しい使用法です。

これらの変更は、container/heap パッケージのAPIの意図と効率的な使用方法をより正確に反映しています。

参考にした情報源リンク

Go言語 container/heap パッケージの公式ドキュメント
Go言語のコミット履歴 (GitHub)
一般的なヒープデータ構造に関する情報 (アルゴリズムとデータ構造の教科書など)
Go言語のポインタとインターフェースに関する一般的な知識I have drafted the detailed explanation. Now I will output it to standard output as requested.

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

このコミットは、Go言語の標準ライブラリである `container/heap` パッケージの `example_pq_test.go` ファイル内のサンプルコードを更新するものです。具体的には、ヒープの不変条件を確立するための `heap.Init` の適切な使用方法と、要素のプロパティが変更された後にヒープを更新するための `heap.Fix` の使用方法を反映しています。

## コミット

`container/heap` パッケージのサンプルコードを更新し、非空のヒープに対してヒープの不変条件を確立するために `Init` を使用し、要素のプロパティが変更された後にヒープを更新するために `Fix` を使用するように修正しました。これは、古いコードが不要な場所で `Init` を使用し、`Fix` が追加された後にサンプルが書かれたため `Fix` を使用していなかった問題を解決します。

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

[https://github.com/golang/go/commit/b2d1a2b513cb9a7ceaa1eb6d097f1ef2a84637dd](https://github.com/golang/go/commit/b2d1a2b513cb9a7ceaa1eb6d097f1ef2a84637dd)

## 元コミット内容

container/heap: update example code

use Init to establish heap invariant on a non-empty heap
use Fix to update heap after an element's properties have been changed

(The old code used Init where it wasn't needed, and didn't use Fix because Fix was added after the example was written.)

LGTM=bradfitz R=adonovan, bradfitz CC=golang-codereviews https://golang.org/cl/94520043


## 変更の背景

このコミットの背景には、`container/heap` パッケージの進化と、それに伴うサンプルコードの陳腐化があります。

元々、`container/heap` パッケージのサンプルコードは、`heap.Fix` 関数が導入される前に書かれていました。`heap.Fix` は、ヒープ内の特定要素の優先度（または値）が変更された際に、ヒープの不変条件を効率的に再確立するための重要な関数です。しかし、この関数が存在しなかったため、古いサンプルコードでは要素の更新を行う際に、一度ヒープから要素を削除し（`heap.Remove`）、そのプロパティを変更した後、再度ヒープに挿入する（`heap.Push`）という非効率な方法が取られていました。

また、`heap.Init` 関数についても、その使用法に関する誤解や不適切な適用が見られました。`heap.Init` は、既存の要素のコレクションからヒープを構築する際に、ヒープの不変条件を確立するために使用されます。しかし、古いサンプルコードでは、既に空のヒープに対して `Init` を呼び出すなど、不要な場所で使用されているケースがありました。

このコミットは、これらの問題を修正し、`container/heap` パッケージの最新の機能と推奨される使用パターンを反映させることを目的としています。これにより、サンプルコードがより効率的で、かつパッケージの意図する正しい使い方を示すものとなります。

## 前提知識の解説

このコミットを理解するためには、以下の概念とGo言語の `container/heap` パッケージに関する知識が必要です。

### 1. ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、特定のヒーププロパティ（不変条件）を満たします。主な種類は以下の通りです。

*   **最小ヒープ (Min-Heap)**: 親ノードの値がその子ノードの値よりも常に小さいか等しい。したがって、根（ルート）ノードがヒープ内の最小値を持つ。
*   **最大ヒープ (Max-Heap)**: 親ノードの値がその子ノードの値よりも常に大きいか等しい。したがって、根ノードがヒープ内の最大値を持つ。

Goの `container/heap` パッケージは、最小ヒープとして実装されており、優先度キューなどの実装に利用されます。ヒープは通常、配列で表現され、特定のインデックス計算によって親子関係が表現されます。

### 2. 優先度キュー (Priority Queue)

優先度キューは、各要素に「優先度」が割り当てられた抽象データ型です。通常のキューとは異なり、要素は追加された順序ではなく、その優先度に基づいて取り出されます。最も優先度の高い要素が最初に取り出されます。ヒープは、優先度キューを効率的に実装するための一般的なデータ構造です。

### 3. Go言語 `container/heap` パッケージ

`container/heap` パッケージは、任意の型をヒープとして扱うための汎用的なインターフェースと関数を提供します。このパッケージを使用するには、`sort.Interface` を実装し、さらに `Push` と `Pop` メソッドを追加で実装する必要があります。

主要な関数は以下の通りです。

*   **`heap.Init(h Interface)`**: `h` がヒープの不変条件を満たすように初期化します。これは、既存の要素のコレクション（例えば、スライス）からヒープを構築する際に使用されます。要素が既にスライスに存在する場合、この関数を呼び出すことで、そのスライスがヒープのプロパティを満たすように再配置されます。
*   **`heap.Push(h Interface, x interface{})`**: 要素 `x` をヒープ `h` に追加し、ヒープの不変条件を維持します。
*   **`heap.Pop(h Interface) interface{}`**: ヒープ `h` から最小（または最大、実装による）要素を削除して返します。ヒープの不変条件は維持されます。
*   **`heap.Remove(h Interface, i int) interface{}`**: ヒープ `h` からインデックス `i` の要素を削除して返します。ヒープの不変条件は維持されます。
*   **`heap.Fix(h Interface, i int)`**: インデックス `i` の要素の優先度（または値）が変更された後、ヒープの不変条件を再確立します。この関数は、要素の値を変更した後に呼び出す必要があります。`Remove` と `Push` を組み合わせるよりも効率的です。

### 4. ヒープの不変条件 (Heap Invariant)

ヒープの不変条件とは、ヒープが常に満たすべきプロパティのことです。最小ヒープの場合、これは「親ノードの値は常にその子ノードの値以下である」という条件です。ヒープに対する操作（追加、削除、更新）が行われた後も、この不変条件が維持されるように、内部的に要素の再配置（ヒープ化操作、heapify）が行われます。

## 技術的詳細

このコミットは、`container/heap` パッケージの `example_pq_test.go` 内の `PriorityQueue` のサンプル実装における2つの主要な改善点に焦点を当てています。

### 1. `heap.Init` の適切な使用

変更前は、`Example_priorityQueue` 関数内で、空の `PriorityQueue` を作成した直後に `heap.Init(pq)` を呼び出していました。

```go
// 変更前
pq := &PriorityQueue{}
heap.Init(pq) // ここでInitを呼び出している
// ... その後、要素をPush

変更後では、まず make を使用して、初期アイテムの数に基づいて PriorityQueue スライスを初期化し、そこに直接アイテムを格納しています。

// 変更後
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
    pq[i] = &Item{
        value:    value,
        priority: priority,
        index:    i, // indexもここで設定
    }
    i++
}
heap.Init(&pq) // 全てのアイテムがスライスに格納された後にInitを呼び出す

2. `heap.Fix` の導入による要素更新の効率化

// 変更前 - updateメソッド
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    heap.Remove(pq, item.index) // 一度削除
    item.value = value
    item.priority = priority
    heap.Push(pq, item) // 再度追加
}

変更後では、この非効率な Remove と Push の組み合わせを heap.Fix に置き換えています。

// 変更後 - updateメソッド
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index) // Fixを呼び出す
}

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

src/pkg/container/heap/example_pq_test.go ファイルにおける変更箇所は以下の通りです。

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -52,13 +52,12 @@ func (pq *PriorityQueue) Pop() interface{} {
 
 // update modifies the priority and value of an Item in the queue.
 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
-	heap.Remove(pq, item.index)
 	item.value = value
 	item.priority = priority
-	heap.Push(pq, item)
+	heap.Fix(pq, item.index)
 }
 
-// This example inserts some items into a PriorityQueue, manipulates an item,
+// This example creates a PriorityQueue with some items, adds and manipulates an item,
 // and then removes the items in priority order.
 func Example_priorityQueue() {
 	// Some items and their priorities.
@@ -66,28 +65,31 @@ func Example_priorityQueue() {
 		"banana": 3, "apple": 2, "pear": 4,
 	}
 
-	// Create a priority queue and put the items in it.
-	pq := &PriorityQueue{}
-	heap.Init(pq)
+	// Create a priority queue, put the items in it, and
+	// establish the priority queue (heap) invariants.
+	pq := make(PriorityQueue, len(items))
+	i := 0
 	for value, priority := range items {
-		item := &Item{
+		pq[i] = &Item{
 			value:    value,
 			priority: priority,
+			index:    i,
 		}
-		heap.Push(pq, item)
+		i++
 	}
+	heap.Init(&pq)
 
 	// Insert a new item and then modify its priority.
 	item := &Item{
 		value:    "orange",
 		priority: 1,
 	}
-	heap.Push(pq, item)
+	heap.Push(&pq, item)
 	pq.update(item, item.value, 5)
 
 	// Take the items out; they arrive in decreasing priority order.
 	for pq.Len() > 0 {
-		item := heap.Pop(pq).(*Item)
+		item := heap.Pop(&pq).(*Item)
 		fmt.Printf("%.2d:%s ", item.priority, item.value)
 	}
 	// Output:

コアとなるコードの解説

`update` メソッドの変更

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -52,13 +52,12 @@ func (pq *PriorityQueue) Pop() interface{} {
 
 // update modifies the priority and value of an Item in the queue.
 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
-	heap.Remove(pq, item.index)
 	item.value = value
 	item.priority = priority
-	heap.Push(pq, item)
+	heap.Fix(pq, item.index)
 }

- heap.Remove(pq, item.index): 変更前は、アイテムの優先度を更新するために、まずヒープからそのアイテムを削除していました。
- heap.Push(pq, item): 削除後、アイテムのプロパティを変更し、再度ヒープにプッシュしていました。この Remove と Push の組み合わせは、アイテムの更新には機能しますが、非効率です。
+ heap.Fix(pq, item.index): 変更後では、heap.Fix 関数が導入されました。アイテムの value と priority を更新した後、heap.Fix を呼び出すことで、指定された item.index の要素がヒープの不変条件を維持するように、効率的にヒープ内で再配置されます。これにより、不要な削除と再挿入のオーバーヘッドがなくなります。

`Example_priorityQueue` 関数の変更

--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -66,28 +65,31 @@ func Example_priorityQueue() {
 		"banana": 3, "apple": 2, "pear": 4,
 	}
 
-	// Create a priority queue and put the items in it.
-	pq := &PriorityQueue{}
-	heap.Init(pq)
+	// Create a priority queue, put the items in it, and
+	// establish the priority queue (heap) invariants.
+	pq := make(PriorityQueue, len(items))
+	i := 0
 	for value, priority := range items {
-		item := &Item{
+		pq[i] = &Item{
 			value:    value,
 			priority: priority,
+			index:    i,
 		}
-		heap.Push(pq, item)
+		i++
 	}
+	heap.Init(&pq)
 
 	// Insert a new item and then modify its priority.
 	item := &Item{
 		value:    "orange",
 		priority: 1,
 	}
-	heap.Push(pq, item)
+	heap.Push(&pq, item)
 	pq.update(item, item.value, 5)
 
 	// Take the items out; they arrive in decreasing priority order.
 	for pq.Len() > 0 {
-		item := heap.Pop(pq).(*Item)
+		item := heap.Pop(&pq).(*Item)
 		fmt.Printf("%.2d:%s ", item.priority, item.value)
 	}
 	// Output:

ヒープの初期化方法の変更:
- 変更前: pq := &PriorityQueue{} で空のヒープを作成し、すぐに heap.Init(pq) を呼び出していました。これは、heap.Init が既存の要素を持つスライスをヒープ化するために設計されているため、不要な呼び出しでした。
- 変更後: pq := make(PriorityQueue, len(items)) を使用して、初期アイテムの数に合わせてスライスを事前に確保しています。その後、ループ内で直接 pq[i] = &Item{...} のようにアイテムをスライスに格納し、item.index も設定しています。全てのアイテムがスライスに格納された後、heap.Init(&pq) を呼び出すことで、スライス全体が一度にヒープの不変条件を満たすように初期化されます。これは、既存のコレクションからヒープを構築する際の正しいパターンです。
heap.Push と heap.Pop の引数変更:
- 変更前は heap.Push(pq, item) や heap.Pop(pq) のように、PriorityQueue のポインタではない値を渡していました。
- 変更後: heap.Push(&pq, item) や heap.Pop(&pq) のように、PriorityQueue のポインタを渡すように修正されています。container/heap のインターフェースはポインタレシーバを持つメソッドを期待するため、これは正しい使用法です。

これらの変更は、container/heap パッケージのAPIの意図と効率的な使用方法をより正確に反映しています。

参考にした情報源リンク

Go言語 container/heap パッケージの公式ドキュメント
Go言語のコミット履歴 (GitHub)
一般的なヒープデータ構造に関する情報 (アルゴリズムとデータ構造の教科書など)
Go言語のポインタとインターフェースに関する一般的な知識

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. ヒープ (Heap)

2. 優先度キュー (Priority Queue)

3. Go言語 `container/heap` パッケージ

4. ヒープの不変条件 (Heap Invariant)

技術的詳細

1. `heap.Init` の適切な使用

2. `heap.Fix` の導入による要素更新の効率化

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

コアとなるコードの解説

`update` メソッドの変更

`Example_priorityQueue` 関数の変更

関連リンク

参考にした情報源リンク

2. `heap.Fix` の導入による要素更新の効率化

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

コアとなるコードの解説

`update` メソッドの変更

`Example_priorityQueue` 関数の変更

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo