티스토리 뷰

반응형

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
}

반응형
댓글
댓글쓰기 폼