使用go提供的接口实现大小堆｜Golang

  package heap

import "container/heap"

        heap包提供了对任意类型（实现了heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树。树的最小元素为其根元素，索引0的位置。

 要用库函数构建一个堆，你必须实现五个方法，即Len() , Less(), Swap(), Push(), Pop。

package main

import (
	"container/heap"
	"fmt"
)

type MyHeap []int

func (m MyHeap) Len() int {
	return len(m)
}

// 如果实现大顶堆，则需要调整一下Less函数
func (m MyHeap) Less(i, j int) bool {
	if m[i] < m[j] {    // m[i] > m[j]
		return true
	}
	return false
}

func (m MyHeap) Swap(i, j int) {
	m[i], m[j] = m[j], m[i]
}

func (m *MyHeap) Push(x any) {
	*m = append(*m, x.(int))
}

func (m *MyHeap) Pop() any {
	val := (*m)[len(*m)-1]
	*m = (*m)[:len(*m)-1]
	return val
}

func main() {
	myHeap := MyHeap{3, 6, 2, 1, 4, 5}
	heap.Init(&myHeap) //如果没有初始值，可以不需要使用此方法
	heap.Push(&myHeap, 7)
	fmt.Println(myHeap) //[1 3 2 6 4 5 7]
	pop := heap.Pop(&myHeap)
	fmt.Println(pop)    //1
	fmt.Println(myHeap) //[2 3 5 6 4 7]
}

/* 没有初始值
func main() {
	myHeap := make(MyHeap, 0)
	heap.Push(&myHeap, 7)
	heap.Push(&myHeap, 2)
	heap.Push(&myHeap, 3)
	heap.Push(&myHeap, 8)
	fmt.Println(myHeap) //[2 7 3 8]
	pop := heap.Pop(&myHeap)
	fmt.Println(pop)    //2
	fmt.Println(myHeap) //[3 7 8]
}
*/