【Go——实现小堆顶】

1. 堆概念

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。

最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者。

最小堆：根结点的键值是所有堆结点键值中最小者。

2. heap

树的最小元素在根部，为index 0.

heap包对任意实现了heap接口的类型提供堆操作。

heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。

3. 类型接口

3.1 类型接口

heap包中核心是heap.Interface接口，堆的基础存储是一个树形结构，可以用数组或是链表实现，通过heap的函数，可以建立堆并在堆上进行操作。

heap.Interface接口源码：

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

sort.Interface接口源码

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

在实现了这些接口之后，就可以被heap包提供的各个函数进行操作，从而实现一个堆。

3.2 成员函数

heap包中提供了几个最基本的堆操作函数，包括Init，Fix，Push，Pop和Remove （其中up, down函数为非导出函数）。这些函数都通过调用前面实现接口里的方法，对堆进行操作。

// 一个堆在使用任何堆操作之前应先初始化。接受参数为实现了heap.Interface接口的对象。
func Init(h Interface)
// 在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。
func Fix(h Interface, i int)
// Push和Pop是一对标准堆操作，Push向堆添加一个新元素，Pop弹出并返回堆顶元素，而在push和pop操作不会破坏堆的结构
func Push(h Interface, x any)
func Pop(h Interface) any
// Remove删除堆中的第i个元素，并保持堆的约束性
func Remove(h Interface, i int) any


//使用案例
import (
	"container/heap"
	"fmt"
)

hp := &ItemHeap{}
heap.Init(hp)
heap.Push(hp, Item{key: i, value: i})
heap.Pop(hp)

3.3 小堆顶的实现

package main

import (
	"container/heap"
	"fmt"
)

// 小堆顶
type Item struct {
	// 排序的关键词,key根据需求修改
	key int
	// value，万能的话可以用interface{}
	value int
}

type ItemHeap []Item

func (h ItemHeap) Len() int {
	return len(h)
}

func (h ItemHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h ItemHeap) Less(i, j int) bool {
	// <是小顶堆，>是大顶堆
	return h[i].key < h[j].key
}

// 实现heap.Interface接口定义的额外方法
func (h *ItemHeap) Push(item interface{}) {
	*h = append(*h, item.(Item))
}

// 这个方法不是给用户使用的
func (h *ItemHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	hp := &ItemHeap{}
	heap.Init(hp)

	for i := 0; i < 10; i++ {
		heap.Push(hp, Item{key: i, value: i})
	}
	for i := 100; i > 90; i-- {
		heap.Push(hp, Item{key: i, value: i})
	}
	// 输出堆的长度，验证元素已插入
	fmt.Printf("Heap length: %d\n", hp.Len())

	//取出最小元素需要使用
	fmt.Println(heap.Pop(hp))
}