GIS Developer

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

Golang은 (고랭지 배추가 생각나..) 기본적으로 데이터 컨테이너로 배열(Array), 슬라이스(Slice), 맵(Map)을 지원합니다. 이 세개의 데이터 컨테이너는 별도의 라이브러리를 import하지 않아도 사용할 수 있는 goland의 기본 요소입니다. 여기에 추가적으로 Linked List 자료구조는 별도의 라이브러를 import 하여 사용할 수 있는데요. 간단히 아래의 예제 코드를 통해 다른 언어를 통해 링크드 리스트를 접해본 개발자라면 쉽게 이해할 수 있을 것입니다.

package main

import (
    "container/list"
    "fmt"
)

func main() {
    ll := list.New()

    ll.PushBack("A")
    ll.PushBack(100)
    ll.PushBack(true)
    ll.PushFront("B")
    ll.PushFront(200)

    for e := ll.Front(); e != nil; e = e.Next() {
        fmt.Printf("[%T] %v\n", e.Value, e.Value)
    }

    fmt.Println("-------------")

    for e := ll.Back(); e != nil; e = e.Prev() {
        fmt.Printf("[%T] %v\n", e.Value, e.Value)
    }
}

링크드리스트 객체는 list.New() 함수 호출을 통해 생성할 수 있습니다. 데이터를 뒷 부분부터 추가(코드 11번~13번)할 수도 있고, 시작 부분에 추가(코드 14번~15번)할 수도 있습니다. 그리고 코드17번~19번처럼 링크드리스트의 시작부터 끝부분까지 순회할 수 있습니다. 이와 반대 방향으로 순회하는 코드는 23번~25번입니다. 실행 결과는 아래와 같습니다.

[int] 200
[string] B
[string] A
[int] 100
[bool] true
-------------
[bool] true
[int] 100
[string] A
[string] B
[int] 200

golang의 링크드 리스트는 배열이나 슬라이스, 맵과는 다르게 지정된 타입의 값만을 추가할 수 없고 모든 타입에 대한 값을 추가한다는 점에 주의해야 합니다.