Go에서 Heap 사용하기

Go의 "containter/heap" 패키지는 heap.Interface를 구현하는 모든 Type에 대해 minheap 기능을 제공한다. MinHeap은 트리(tree)로서 가장 작은 값이 Root에 오게 되며, 또한 각 노드는 그 노드의 서브트리(subtree)보다 작은 값을 갖는 구조를 갖는다. 이러한 MinHeap에서 모든 요소를 루트로부터 차례로 Pop하게 되면, 가장 작은 값부터 올림차순으로 소트된 값들을 얻게 된다.

heap 패키지는 heap.Interface 인터페이스를 구현하는 Type을 상대로 동작하므로 heap을 사용하기 위해 heap.Interface 인터페이스를 구현한 새로운 사용자 Type을 만들어야 한다. heap.Interface는 다음과 같은 5개의 메서드를 갖는 인터페이스이다.

예를 들어, 정수 슬라이스를 기반으로 하는 IntHeap을 정의하기 위해 다음과 같이 5개의 메서드를 구현할 수 있다.

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
  	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(element interface{}) {
	*h = append(*h, element.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	element := old[n-1]
	*h = old[0 : n-1]
	return element
}

heap.Interface 인터페이스를 구현한 Type 오브젝트에 대해 heap을 사용하기 위해서는 먼저 heap.Init() 메서드를 호출하여 힙을 초기화해야 한다. 힙이 초기화된 후에 Push() 메서드를 사용하여 힙에 데이타를 추가하거나 Pop()을 사용하여 루트 노드를 하나 읽고 제거할 수 있다.

package main

import (
	"container/heap"
	"fmt"
)

/* IntHeap 인터페이스 구현 여기에 추가 */

func main() {
	h := &IntHeap{2, 1, 7}
	heap.Init(h)
	fmt.Println(*h) // 1 2 7

	heap.Push(h, 4)
	heap.Push(h, 10)

	fmt.Println(*h) // 1 2 7 4 10

	// 1 2 4 7 10
	for h.Len() > 0 {
		m := heap.Pop(h)
		fmt.Print(m, " ")
	}
}

위의 예제를 보면, heap.Init()을 통해 초기 데이타 2,1,7을 추가하였다. 다음으로 힙에 4,10 두개의 데이타를 추가하였고, 힙의 값을 모두 출력해 보았다. 이때 힙은 1 2 4 7 10 이 아닌 1 2 7 4 10 인데, 이는 힙의 속성상 상위노드가 서브노드보다 적기만 하면 되지 굳이 4와 7을 순서대로 정렬될 필요는 없기 때문이다. 아래 두번째 그림을 보면, 4와 10 이 추가되었을 때의 트리구조가 어떤 모습인 지 알 수 있다. 물론 10이 7의 Child 노드로 있어도 힙의 속성을 거스리는 것이 아니므로 문제가 없다.

힙에서 Pop()을 호출하여 루트노드(1)를 제거하면, 1 밑에 있던 2와 7중 작은 값인 2가 루트로 올라가며, 2가 제거되면 4와 7중 4가 루트로 올라간다. 이처럼 힙은 Pop()으로 인해 (혹은 Push로 인해) 노드의 위치를 바꾸면서 힙의 속성을 유지하도록 트리구조를 변경하게 된다. 위의 예제 마지막 문장처럼 힙의 모든 값을 Pop하여 출력하게 되면, 1 2 4 7 10와 같이 올림차순의 데이타를 갖게 된다.