Golang으로 Min Heap을 구현해보자 - container/heap 패키지 사용

Photo by Markus Spiske on Unsplash

 

이번에는 container/heap 패키지를 이용해서 구현해보자

"요구사항만 만족해주면 원하는 heap 기능을 제공하겠다." 이렇게 한 줄 요약할 수 있겠다. (Fix, Remove 등의 기능도 있지만 이것은 생략하겠다.)

 

이전 포스팅한 from the scratch 구현

- https://jusths.tistory.com/215

- https://play.golang.org/p/cjYXpQjPiZY

 

container/heap을 이용한 구현

- https://play.golang.org/p/JwU6aHNGb7k

 

요구사항과 제공기능

https://golang.org/pkg/container/heap/#Interface

 

어떠한 타입이건 sort.Inerface 와 Push, Pop 메서드만 구현하면 min heap을 제공하겠다는 것이다. sort.Interface는 Len, Less, Swap 메서드 구현을 요구하니 구현해야할 메서드는 총 5개이다. min heap을 제공한다는 것은 무슨 의미일까? 아래에 언급한 invariants를 만족하는 슬라이스를 제공하겠다는 것이다.

 

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

 

요구하는 메서드를 하나씩 만들어보자. 이번에도 지난 번에 구현했던 슬라이스를 값으로 가지는 슬라이스를 구현하겠다.

 

Len, Less, Swap, Push, Pop 메서드

Len, Less, Swap 까지는 간단하다. 이해하기 어려운 부분이 없다

type MinHeap struct {
	nodes [][]int
}

func (h *MinHeap) Len() int {
	return len(h.nodes)
}

func (h *MinHeap) Less(i, j int) bool {
	if h.nodes[i][0] != h.nodes[j][0] {
		return h.nodes[i][0] < h.nodes[j][0]
	}
	return h.nodes[i][1] < h.nodes[j][1]
}

func (h *MinHeap) Swap(i, j int) {
	h.nodes[i], h.nodes[j] = h.nodes[j], h.nodes[i]
}

 

중요한건 Push와 Pop이다. 어떤걸 구현해줘야 한다는 걸까? container/heap 내의 구현을 봐야 한다.

우리가 나중에 heap.Push, heap.Pop 함수를 실행하면 어떤 동작을 하는지를 봐야 한다. 아래는 실제 패키지 내 코드이다. 헷갈리지 말자. 우리가 구현해야할 메서드가 아니라 heap 패키지 내의 함수인 Push, Pop이다. 

Push(x interface{})

heap.Push는 우리가 만든 Push메서드를 먼저 실행하고, heap 패키지 내의 up 함수를 실행한다

우리가 구현할 Push 메서드는 기존의 heap 맨 뒤에 새로운 값을 추가만 해주면 된다.

Pop() interface{}

heap.Pop은 0번 인덱스와 맨 끝 인덱스의 값을 바꾼 다음에, down 함수를 실행한다. down(h, 0, n)은 h라는 heap의 길이가 n이라고 했을때에 0번 인덱스부터 heap invariants를 을 의미한다

그리고 마지막으로 h.Pop()을 실행한다.

 

우리가 구현할 Pop 메서드는

 

1) 먼저 heap의 맨 마지막 값을 추출해두고

2) heap의 전체 길이를 하나 줄이면 된다.

func (h *MinHeap) Push(x interface{}) {
	h.nodes = append(h.nodes, x.([]int))
}

func (h *MinHeap) Pop() interface{} {
	result := h.nodes[len(h.nodes)-1]
	h.nodes = h.nodes[:len(h.nodes)-1]
	return result
}

끝