go에서 패키지 라이브러리로 제공하는 힙 자료구조가 있습니다. 제공되는 힙 자료구조는 부모 노드의 값은 자식 노드의 값보다 반드시 작거나 같다라는 조건을 충족해야 합니다. 이러한 조건 충족을 비교 매서드와 힙 자료구조에 요소를 추가(Push)하고 가져오는(Pop) 매서드 등을 제공하는 heap.Interface 인터페이스를 직접 구현한 Custom Type 소스 코드를 작성해야 합니다.
만약 정수형 값을 요소로 하는 힙 자료구조를 만든다고 할때 heap.Interface 인터페이스를 구현하는 Custom Type은 다음과 같습니다.
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(elem interface{}) {
*h = append(*h, elem.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
elem := old[n-1]
*h = old[0 : n-1]
return elem
}
heap.Interface에서 구현해야 하는 매서드는 아래와 같습니다.
| 매서드 |
설명 |
| func (h IntHeap) Less(i, j int) bool |
i와 j 번째 요소의 값을 비교하여 i번째 요소가 j번째 요소보다 작으면 true을 반환 |
| func (h IntHeap) Len() int |
요소의 개수를 반환 |
| func (h IntHeap) Swap(i, j int) |
i번째와 j번째 요소의 값을 서로 바꿈 |
| func (h *IntHeap) Push(elem interface{}) |
요소의 값을 추가 |
| func (h *IntHeap) Pop() interface{} |
요소의 값을 가져옴(작은 값 순서로 값이 얻어짐) |
이제 위의 IntHeap을 사용하는 소스 코드를 살펴 보면 아래와 같습니다.
// main
package main
import (
"container/heap"
"fmt"
)
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(elem interface{}) {
*h = append(*h, elem.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
elem := old[n-1]
*h = old[0 : n-1]
return elem
}
func main() {
h := &IntHeap{9, 6, 4, 1}
heap.Init(h)
fmt.Println(*h)
fmt.Println("---------------")
heap.Push(h, 7)
heap.Push(h, 9)
heap.Push(h, 11)
for h.Len() > 0 {
m := heap.Pop(h)
fmt.Print(m, " ")
}
}
앞서 설명한 코드에 대한 설명은 하지 않고 main 함수를 살펴보면.. 먼저 37번 코드에서 힙 데이터로 구성할 요소들에 대한 슬라이스 객체를 생성합니다. 그리고 38번에서 이 슬라이스 객체를 통해 heap 객체로 초기화합니다. 그리고 43번~45번 코드에서 다시 몇개의 데이터를 더 추가하고 47번의 for 문을 통해 힙의 요소를 순서대로 출력해보면 작은 값에서 점점 큰 값이 얻어지는 것을 볼 수 있습니다. 위의 코드에 대한 실행 결과는 아래와 같습니다.
[1 6 4 9]
---------------
1 4 6 7 9 9 11
이 글은 예제로 배우는 GO 프로그래밍에서 학습한 코드를 제가 이해한 내용을 덧붙여 정리한 글입니다.
