Golang에서 표준 라이브러리를 이용해 최소·최대힙 구현하기

package heap

// 편의상 모두 풀어서 적었지만, 실제 인터페이스는 sort.Interface를 임베드하고 있다.
type Interface interface {
    Len() int           // 힙의 길이를 반환
    Less(i, j int) bool // i번째 요소가 j번째 요소보다 작으면 true
    Swap(i, j int)      // i번째 요소와 j번째 요소를 교환
    Push(x any)         // 힙에 새로운 요소를 추가
    Pop() any           // 힙에서 가장 작은 요소를 제거하고 반환
}

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap - int 타입의 슬라이스를 힙으로 구현한 구조체이다.
type IntHeap []int

// Len - 힙의 길이를 반환한다.
func (h *IntHeap) Len() int {
	return len(*h)
}

// Less - i번째 요소가 j번째 요소보다 작으면 true를 반환한다.
// NOTE: 정렬 기준을 변경하고 싶을 때 해당 메서드를 사용할 수 있다. 
// 특정 구조체 힙이라면 구조체의 특정 필드: ex) `(*h)[i].Field < (*h)[j].Field` 와 같이 작성하면 된다. 
func (h *IntHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}

// Swap - i번째 요소와 j번째 요소를 교환한다. 실제 힙에서는 Upheap과 Downheap을 구현하기 위해 사용한다
func (h *IntHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

// Push - 힙에 새로운 요소를 추가한다.
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

// Pop - 힙에서 가장 작은 요소를 제거하고 반환한다.
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	// IntHeap을 초기화한다.
	h := &IntHeap{2, 1, 5, 3, 4}
	heap.Init(h) // 힙을 초기화한다.

	// 힙에 새로운 요소를 추가한다.
	heap.Push(h, 0)

	for h.Len() > 0 {
		fmt.Println(heap.Pop(h)) // 힙에서 가장 작은 요소를 제거하고 출력한다.
	}
}