数据结构之堆

满足下列性质：
1）一颗树深度为h，最大层数为k，深度与最大层数相同，k=h；
2）叶子节点数（最后一层）为2k−1；
3）第 i 层的节点数是：2i−1；
4）总节点数是：2k-1，且总节点数一定是奇数。

[ 10, 7, 2, 5, 1 ]

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2 // right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置

Node	Array index (i)	    Parent index	  Left child	Right child
10	     0	                   -1	              1	             2
7	     1	                    0	              3	             4
2	     2	                    0	              5	             6
5	     3	                    1	              7	             8
1	     4	                    1	              9	             10

array:  10    7    2    5     1
index:  0     1    2    3     4
level:  1     2    2    3     3

完全二叉树适合用数组存储，因为下标为 i 的元素，它的左子树下标为 2i, 右子树下标为 2i+1。父节点就是 i/2 的
parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2 // right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置

[ 10, 14, 25, 33, 81, 82, 99 ]

// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
//	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

// 在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。复杂度O(log(n))，其中n等于h.Len()。
func Fix(h Interface, i int) 

//初始化一个堆。一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。
func Init(h Interface) 

//删除并返回堆h中的最小元素（不影响约束性）。复杂度O(log(n))，其中n等于h.Len()。该函数等价于Remove(h, 0)。
func Pop(h Interface) interface{} 

//向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
func Push(h Interface, x interface{}) 

//删除堆中的第i个元素，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
func Remove(h Interface, i int) interface{} 

package heap_test

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
	// Output:
	// minimum: 1
	// 1 2 3 5
}

// 调整比较的逻辑 这是小顶堆, 前面的元素 堆顶 要比 后面的都小
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }

// 如果是大顶堆, 前面的元素 堆顶 要比 后面的都大
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }

2021.7.31  11:30    TaskA
2021.8.1   1:20     TaskB
2021.8.1   1:21     TaskC
2021.8.1   23:23    TaskD

import (
	"container/heap"
	"fmt"
)


type Item struct {
	value    string // 优先级队列中的数据，可以是任意类型，这里使用string
	priority int    // 优先级队列中节点的优先级
	index    int    // index是该节点在堆中的位置
}

// 优先级队列需要实现heap的interface
type PriorityQueue []*Item

// 绑定Len方法
func (pq PriorityQueue) Len() int {
	return len(pq)
}

// 绑定Less方法，这里用的是小于号，生成的是小根堆
// 交换的标准是 优先级
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

// 绑定swap方法
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index, pq[j].index = i, j
}

// 绑定push方法
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)

    // 标记该元素的索引位置
	n := len(*pq)
	item.index = n

	*pq = append(*pq, item)
}

// 绑定put方法，将index置为-1是为了标识该数据已经出了优先级队列了
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)

	item := old[n-1]
	*pq = old[0 : n-1]
	item.index = -1
	return item
}

// 更新修改了优先级和值的item在优先级队列中的位置
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func TestPriorityQueue() {
	// 创建节点并设计他们的优先级
	items := map[string]int{"TaskA": 5, "TaskB": 3, "TaskC": 9}
	i := 0
	pq := make(PriorityQueue, len(items)) // 创建优先级队列，并初始化
	for k, v := range items {             // 将节点放到优先级队列中
		pq[i] = &Item{
			value:    k,
			priority: v,
			index:    i}
		i++
	}
	heap.Init(&pq) // 初始化堆
	item := &Item{ // 创建一个item
		value:    "TaskD",
		priority: 1,
	}
	heap.Push(&pq, item)           // 入优先级队列
	pq.update(item, item.value, 6) // 更新item的优先级
	for len(pq) > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s index:%.2d\n", item.priority, item.value, item.index)
	}
}