Go에서 `container/heap`을 사용하여 우선 순위 대기열 구현하기

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이 가장 높은 우선 순위를 제공하도록 하려면 여기에서 greater than을 사용합니다.
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는 대기열에서 Item의 우선 순위와 값을 수정합니다.
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 메서드를 사용자 정의하면 우선 순위 대기열이 최소 힙 또는 최대 힙으로 작동하는지 여부를 정의할 수 있습니다. 이 경우 최대 힙을 사용하여 우선 순위가 높은 항목이 먼저 대기열에서 제거되도록 했습니다.