[Go] Heap 자료구조를 사용하는 우선순위 큐 (Priority Queue)

서론

Go 에는 Priority Queue가 없다. 심지어 Queue 조차 없다. 그 이유는 예상컨데 너무 쉽게 Queue라 불리우는 자료구조를 구현할 수 있기 때문이 아닐까 싶다. 아무리 쉽지만 이해하지 않고 사용한다면 쉽게 느껴지지 않을테다.

내가그랬다.. 우선순위큐를 사용해야한다면 다른 언어를 통해 알고리즘을 풀어버린 나약한 선택을 했다..

간단히 공부를 하고보니 예전에 예제를 보며 왜 이 복잡한 일을 개발자에게 맡기는거야! 라고 생각했지만 그 정도로 복잡한 내용이 아니었다.
살펴보자.

Priority Queue 란?

FIFO(First In First Out)의 특징을 가지는 자료구조인 Queue. 이 Queue 자료구조에서 우선순위를 주어 힙을 통해 우선순위를 기준으로 O(nlogn)의 시간 복잡도를 통해 정렬해 주는 자료구조.

도큐먼트의 PriorityQueue 구현 예제

(https://golang.org/src/container/heap/example_pq_test.go)

// An Item is something we manage in a priority queue.
type Item struct {
    value    string // The value of the item; arbitrary.
    priority int    // The priority of the item in the queue.
    // The index is needed by update and is maintained by the heap.Interface methods.
    index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

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

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    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 interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

잠깐! 뒤로가기 누르지마세요! 쫄지마세요!

이전의 나에게..

코드 분석

일딴 어떠한 것들이 사용됐고 만들어진 함수가 어떠한 것들이 있는지 살펴보자.
우선 queue에 담을 object인 item이 필요하다. (당근)
이 item에 따라 Generic이.. 있긴하지만 아직 난 잘 모르겠는 Go에서는 함수를 알맞게 오버라이딩하여 바꾸어 주어야한다. (제네릭이 생겼다네..? 그건 나중에 공부해 보아야지)
구현해 놓은 함수를 살펴보자.

1. Len()int
2. Less(int,int)bool
3. Swap(int,int)
4. Push(interface{})
5. Pop() interface{}
6. update()

반드시 구현하여아하는 함수는 1번 ~ 5번 함수 5개 이다.
그 이유는 Heap 자료구조를 통해 구현되는 Priority Queue의 특성에 따른 것이라 할 수 있다.

나는 두개로 나누어 이를 설명하고 싶다.

heap.Interface

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}

heap 패키지의 Interface는 sort의 Interface를 임베딩하고 있는것을 볼 수 있다.
그리고 Push와 Pop
interface를 사용하기 위해선 interface가 가진 함수를 모두 구현하여야 하는 것을 알고 계실거라 생각하겠다.

sort.Interface

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

sort의 Inteface는 Len, Less, Swap 이렇게 세가지의 함수를 가지고 있다.
왜 다섯가지의 함수를 반드시 구현하여야 하는지 알 수 있는 부분!

함수 분석

Len()int

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

object의 len()값을 출력하는 함수.

Less(int, int)bool

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].priority > pq[j].priority
}

우선순위를 줄 데이터의 기준과 정렬 종류(오름차순, 내림차순)을 결정하는 함수.
여기서는 주석으로도 잘 설명돼 있듯 객체가 가진 priority라는 값을 기준으로 큰 값을 우선적으로 놓는다. 내림차순이라는 말. 반대로 오름차순으로 정렬하고프면 부등호의 모양을 반대로 하면 된다.

Swap(int, int)

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

pq 타입에 속한 객체의 순서를 바꾸는 함수.
여기까지가 sort에 필요한 함수이다. 이 세가지를 모두 만족하면 sort.Interface 의 조건에 부합하게 된다.
이 다음은 Heap을 사용하는 Priority Queue이기에 구현하여야 하는 부분.

Push(interface{})

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

값을 Heap에 넣기 위한 함수.
inteface형태로 매개변수를 넘겨 주기에 넘겨 받은 데이터가 Item 타입이라는 것을 x.(Item)과 같이 알려준다.
그리고 append를 통해 pq에 담아준다.

Pop()interface{}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

pq에서 가장 우선 순위가 높은 값을 빼 내는 함수.
old[n-1] = nil을 하지 않는다면 go의 GC는 이 값을 쓰레기 값이라 생각히자 않기에 메모리 누수가 생길 수 있으니 반드시 필요한 부분이다.
그리고 pq의 길이를 하나 줄이며 끝 낸다!

마무리

생각보다 간단하지 과거의 나야.. 피하지마 ㅠㅠ