1. heap 接口定义
heaptype Interface interface {
sort.Interface
/*
sort.Interface:
Len() int //返回堆的长度
Less(i, j int) bool //比较索引i的元素和索引j元素的大小
Swap(i, j int) //交换索引i和索引j的元素
*/
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
2. 堆向上调整算法
func up(h Interface, j int) {
for {
i := (j - 1) / 2 //堆的特性，索引的j的父节点索引 = (j - 1) / 2
//如果 已经到的堆的
/*结束条件
1.父亲<=小的孩子则停止
2.已经调整到堆的根节点
*/
if i == j || !h.Less(j, i) {
break
}
//交换索引i和索引j的元素
h.Swap(i, j)
j = i
}
}
3.向下调整算法
func down(h Interface, i0, n int) bool {
i := i0
for {
j1 := 2*i + 1 //堆特性，节点i的左子节点= 2*i + 1 ，节点i的左子节点= 2*i + 2
/*
结束条件：
1、父亲<=小的孩子则停止
2、调整到叶子节点，（叶子节点特征为没有左孩子，就是数组下标超出了范围）
*/
if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
break
}
j := j1 // left child
if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
j = j2 // = 2*i + 2 // right child
}
if !h.Less(j, i) {
break
}
h.Swap(i, j)
i = j
}
return i > i0
}
1.实现heap接口
/*
最小堆的实现
*/
type minHeap []int
func (h minHeap) Len() int {
return len(h)
}
func (h minHeap) Less(i, j int) bool {
//最小堆
return h[i] < h[j]
//最大堆
//return h[i] < h[j]
}
/*
实现Swap 交换index i和index j的元素
*/
func (h *minHeap) Swap(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
/*
实现push 结构将元素push到堆中
*/
func (h *minHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
/*
实现pop 结构将元素push到堆中
*/
func (h *minHeap) Pop() interface{} {
res := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return res
}2.调用heap
func main() {
h := make(minHeap, 0)
heap.Init(&h)
heap.Push(&h, 1)
heap.Push(&h, 2)
heap.Push(&h, 10)
heap.Push(&h, 3)
heap.Push(&h, 4)
heap.Push(&h, 6)
for len(h) != 0 {
fmt.Println(heap.Pop(&h))
}
}