堆

什么是堆

堆是一个满足特定条件的完全二叉树，完全二叉树又很适合使用数组来实现。

堆的实现

基本步骤就是

• 实现获取父子节点的逻辑
• 入堆，实现从堆底交换的逻辑
• 出堆，先首位交换，然后实现从堆顶到堆底的交换逻辑

package main  
  
import "fmt"  
  
// 这里我们创建一个任意类似的数组，因为在实际业务中，我们数据很可能是各种对象等类型  
type intHead []any  
  
// 索引获取  
func (h *intHead) left(i int) int {  
    return 2*i + 1  
}  
  
func (h *intHead) right(i int) int {  
    return 2*i + 2  
}  
  
func (h *intHead) parent(i int) int {  
    return (i - 1) / 2  
}  
  
// 获取堆顶  
func (h *intHead) peek() any {  
    return (*h)[0]  
}  
  
// 入堆，本质上进行堆化  
func (h *intHead) push(val any) {  
    //先安置到最底部，即数组的最后  
    *h = append(*h, val)  
    index := len(*h) - 1  
    //进行堆化，即较父节点大小  
    var parentIndex int  
    for true {  
       parentIndex = h.parent(index)  
       if parentIndex < 0 || (*h)[parentIndex].(int) >= (*h)[index].(int) {  
          break  
       }  
       //父子交换  
       (*h)[parentIndex], (*h)[index] = (*h)[index], (*h)[parentIndex]  
       index = parentIndex  
    }  
}  
  
// 出堆，即我们要获取最大值  
func (h *intHead) pop() any {  
    if len(*h) == 0 {  
       return nil  
    }  
    //交换堆顶和堆底的数值，方便后续维持堆化  
    data := (*h)[0]  
    (*h)[0], (*h)[len(*h)-1] = (*h)[len(*h)-1], (*h)[0]  
    (*h) = (*h)[:len(*h)-1]  
    //进行堆化  
    var leftIndex, rightIndex, maxIndex, nodeIndex int  
    nodeIndex = 0  
    for true {  
       leftIndex = h.left(nodeIndex)  
       rightIndex = h.right(nodeIndex)  
       //超出界限  
       if rightIndex > len(*h)-1 {  
          break  
       }  
       //子节点都比父节点小  
       if (*h)[nodeIndex].(int) >= (*h)[leftIndex].(int) && (*h)[nodeIndex].(int) >= (*h)[rightIndex].(int) {  
          break  
       }  
  
       if (*h)[leftIndex].(int) > (*h)[rightIndex].(int) {  
          maxIndex = leftIndex  
       } else {  
          maxIndex = rightIndex  
       }  
       (*h)[nodeIndex], (*h)[maxIndex] = (*h)[maxIndex], (*h)[nodeIndex]  
       nodeIndex = maxIndex  
    }  
    return data  
  
}  
func main() {  
    // 测试数据  
    heap := make(intHead, 0)  
  
    // 插入一些数据  
    heap.push(5)  
    heap.push(3)  
    heap.push(8)  
    heap.push(1)  
    heap.push(2)  
    heap.push(7)  
    heap.push(4)  
  
    for len(heap) > 0 {  
       fmt.Println("Pop:", heap.pop())  
       fmt.Println("Heap after pop:", heap)  
    }  
}

但我们实际上我们使用go，是没有这么麻烦的，因为go本身是提供了container/heap这个库来实现了堆的操作。

package main  
  
import (  
    "container/heap"  
    "fmt")  
  
// IntHeap 是一个由整数构成的最小堆  
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{}) {  
    *h = append(*h, x.(int))  
}  
  
// 出堆  
func (h *IntHeap) Pop() interface{} {  
    x := (*h)[len(*h)-1]  
    *h = (*h)[:len(*h)-1]  
    return x  
}  
  
func main() {  
    h := &IntHeap{2, 1, 5}  
    heap.Init(h)  
    heap.Push(h, 3)  
  
    for h.Len() > 0 {  
       fmt.Printf("%d ", heap.Pop(h))  
    }  
}

其实本身container/heap保证了堆本身结构的有序。具体的排序和出入堆逻辑都需要我们来进行实现，确保了灵活度，来保证实际业务逻辑编写中的可用性。

问题

为什么出堆的时候要首位交换，因为直接弹出堆顶会很难再保持堆的结构，要改动数组后续所有的位置。