[Golang] Heap 자료구조

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 프로그래밍에서 학습한 코드를 제가 이해한 내용을 덧붙여 정리한 글입니다.

답글 남기기 응답 취소