우선 순위 큐. [11279]

[1. go heap 구현]

go 에서 heap 을 사용하기 위해서는

container/heap 패키지를 사용해야 하며,

 

사용자가 정의한 heap 타입은 아래와 같이 몇가지 interface 들의 함수를 구현해야 한다.

• (h MinHeap) Len() int
  => heap 의 길이를 반환한다.
  => slice 길이를 반환하도록 한다.
  
  
• (h MinHeap) Less(parent, child int) bool
  => 보통의 heap 구현이 마지막 child 를 parent 와 비교해나가면서 루트로 올라가는 방식이며,
  => parent 와 child 간 값을 비교하여 parent 의 우선순위가 더 높은 경우 true 를 반환하도록 한다.
  => child 와 parent 간 swap 이 필요하지 않는 경우 true 를 반환하도록 한다.
  
  
• (h MinHeap) Swap(parent, child int)
  => swap 코드를 작성하면 된다. 
  
  
• (h *MinHeap) Push(x interface{})
  => heap (slice) 에 값을 append 하도록 한다.
  
  
• (h *MinHeap) Pop() interface{}
  => 보통의 heap 구현이 index: 1 이 root 인 경우가 많은데,
  => go 에서는 마지막 index 에 root 가 위치하는 것 같다.
  => 마지막 인덱스의 값을 반환하도록 하고,
  => 원래 heap (slice) 는 마지막 값을 빼도록 reslice 하도록 한다.

 

위에서 구현한 함수는 Len() 을 제외하고서는 직접 호출하지 않고,

container/heap 이 제공하는 함수 내부에서 사용되므로

container/heap 패키지를 사용하여 heap 을 초기화, push, 그리고 pop 할 수 있도록 한다.

 

 

[2. 코드]

 

 

[3. heapify]

heap 내부의 값이 변경될 경우 (다익스트라 같은 알고리즘 상에서)

heap 구조가 유지되지 않을 수 있으므로, heapify 가 필요하다.

이 경우 container/heap 패키지에서 Fix(h interface, i int) 함수를 사용하도록 한다.

 

이 함수는 heap 의 주소값과,

heap 에서 변경된 위치의 index 를 필요로 한다,

 

func main() {
	h := MinHeap{20, 15, 7, 3, 2}
	heap.Init(&h)

	// [2 3 7 20 15]
	fmt.Println(h)

	h[0] = 99
	heap.Fix(&h, 0)
	// [3 15 7 20 99]
	fmt.Println(h)

	h[3] = 1
	heap.Fix(&h, 3)
	// [1 3 7 15 99]
	fmt.Println(h)
}

 

위 예제에서 heap 구조가 변경된 것을 확인 할 수 있다.

heapify 시간복잡도는 O(logn) 이다.