`container/heap`を使ったGoにおける優先度キューの実装

Key Takeaways

Goには組み込みの優先度付きキューはありませんが、container/heapパッケージを使用して実装できます。
優先度は、ヒープ順序（最小ヒープまたは最大ヒープ）を定義するためにLess()メソッドをカスタマイズすることで制御されます。
ヒープインターフェースは、ソートおよびキューの変更メソッド（Push、Popなど）の実装を必要とします。

優先度付きキューは、各要素に関連付けられた優先度を持つ抽象データ構造です。要素は優先度に基づいて処理され、優先度の高い要素が優先度の低い要素よりも先にデキューされます。Goでは、container/heapパッケージは、ヒープインターフェースを使用して優先度付きキューを実装する方法を提供します。

ヒープインターフェースの理解

container/heapパッケージは、heap.Interfaceを実装する型で動作します。このインターフェースには、次のメソッドが必要です。

type Interface interface {
    sort.Interface
    Push(x any) // add x as element Len()
    Pop() any   // remove and return element Len() - 1.
}

このインターフェースを実装することで、優先度付きキューのカスタム動作を定義できます。

優先度付きキューの実装

優先度付きキューを作成するには、優先度フィールドを含む、保存するアイテムの構造体を定義します。次に、これらのアイテムへのポインターのスライスでheap.Interfaceを実装します。

package main

import (
    "container/heap"
    "fmt"
)

// Itemは優先度付きキューの要素を表します。
type Item struct {
    value    string // アイテムの値。
    priority int    // アイテムの優先度。
    index    int    // ヒープ内のアイテムのインデックス。
}

// PriorityQueueはheap.Interfaceを実装し、Itemsを保持します。
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// Popが最高の優先度を返すように、ここではより大きいものを使用します。
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // 安全のため
    *pq = old[0 : n-1]
    return item
}

// updateは、キュー内のアイテムの優先度と値を変更します。
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

func main() {
    // 優先度付きキューを作成し、いくつかのアイテムを追加します。
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    items := map[string]int{
        "banana": 3,
        "apple":  2,
        "pear":   4,
    }

    for value, priority := range items {
        heap.Push(&pq, &Item{
            value:    value,
            priority: priority,
        })
    }

    // アイテムの優先度を更新します。
    item := &Item{
        value:    "orange",
        priority: 1,
    }
    heap.Push(&pq, item)
    pq.update(item, item.value, 5)

    // 優先度付きキューからアイテムを削除します。
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("%s: %d\n", item.value, item.priority)
    }
}

この例は、container/heapパッケージを使用してGoで優先度付きキューを実装する方法を示しています。Lessメソッドをカスタマイズすることで、優先度付きキューを最小ヒープまたは最大ヒープとして動作させるかどうかを定義できます。この場合、優先度の高いアイテムが最初にデキューされるように、最大ヒープを使用しました。