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

Key Takeaways

1. Go에는 기본 제공 우선 순위 대기열이 없지만 container/heap 패키지를 사용하여 구현할 수 있습니다.
2. 우선 순위는 Less() 메서드를 사용자 정의하여 힙 순서(최소 힙 또는 최대 힙)를 정의하여 제어됩니다.
3. 힙 인터페이스는 정렬 및 대기열 변경 메서드(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 메서드를 사용자 정의하면 우선 순위 대기열이 최소 힙 또는 최대 힙으로 작동하는지 여부를 정의할 수 있습니다. 이 경우 최대 힙을 사용하여 우선 순위가 높은 항목이 먼저 대기열에서 제거되도록 했습니다.

FAQs

Go의 heap.Interface는 최소 힙과 최대 힙 모두에 사용할 수 있습니까?

예, Less() 함수를 사용자 정의하여 가능합니다. 최대 힙의 경우 i > j를 반환하고, 최소 힙의 경우 i < j를 반환합니다.

Item 구조체에 index 필드가 필요한 이유는 무엇입니까?

index는 우선 순위가 변경될 때 heap.Fix가 요소의 위치를 효율적으로 업데이트하는 데 도움이 됩니다.

heap.Pop()은 항상 가장 높은 우선 순위 항목을 반환합니까?

예, Less()가 최대 힙에 적합하게 정의된 경우입니다.

Leapcell은 Go 프로젝트 호스팅을 위한 최고의 선택입니다.

Leapcell은 웹 호스팅, 비동기 작업 및 Redis를 위한 차세대 서버리스 플랫폼입니다.

다국어 지원

• Node.js, Python, Go 또는 Rust로 개발하십시오.

무료로 무제한 프로젝트 배포

• 사용량에 대해서만 지불하십시오. 요청도 없고, 비용도 없습니다.

탁월한 비용 효율성

• 유휴 비용 없이 사용한 만큼 지불하십시오.
• 예: $25는 평균 응답 시간 60ms에서 694만 건의 요청을 지원합니다.

간소화된 개발자 경험

• 간편한 설정을 위한 직관적인 UI.
• 완전 자동화된 CI/CD 파이프라인 및 GitOps 통합.
• 실행 가능한 통찰력을 위한 실시간 메트릭 및 로깅.

손쉬운 확장성 및 고성능

• 높은 동시성을 쉽게 처리할 수 있는 자동 확장.
• 운영 오버헤드가 전혀 없습니다. 구축에만 집중하십시오.

설명서에서 더 많은 것을 알아보십시오!

X에서 팔로우하세요: @LeapcellHQ