二叉堆是一棵满二叉树，父节点的值大于子节点。
用数组存储二叉堆，假如一个节点的下标为k，那么这个节点的左孩子就是2k，右孩子就是2k+1。
用Go语言实现如下：
package heap
import (
"fmt"
)
// MaxHeap 大顶堆
type MaxHeap struct {
data []int
}
// Init 初始化
func (heap *MaxHeap) Init(maxSize int) {
heap.data = make([]int, 0, maxSize)
heap.data = append(heap.data, 0)
}
// Size 堆的长度
func (heap MaxHeap) Size() (size int) {
size = len(heap.data) - 1
return
}
// IsEmpty 堆是否为空
func (heap MaxHeap) IsEmpty() bool {
return heap.Size() == 0
}
// Insert 插入一个元素
func (heap *MaxHeap) Insert(item int) {
heap.data = append(heap.data, item)
heap.shiftUp(heap.Size())
}
// Extract 删除一个元素
func (heap *MaxHeap) Extract() int {
item := heap.data[1]
heap.data[1], heap.data[heap.Size()] = heap.data[heap.Size()], heap.data[1]
heap.data = heap.data[:len(heap.data)-1]
if !heap.IsEmpty() {
heap.shiftDown(1)
}
return item
}
// shiftUp 向上调整堆的结构
// 优化：不用每次都交换
func (heap *MaxHeap) shiftUp(k int) {
temp := heap.data[k]
for k > 1 && heap.data[k/2] < temp {
heap.data[k/2] = heap.data[k]
k /= 2
}
heap.data[k] = temp
}
// shiftDown 向下调整堆的结构
// 优化：不用每次都交换
func (heap *MaxHeap) shiftDown(k int) {
temp := heap.data[k]
for k*2 <= heap.Size() {
j := 2 * k
if j+1 <= heap.Size() && heap.data[j+1] > heap.data[j] {
j = j + 1
}
if temp >= heap.data[j] {
break
}
heap.data[k] = heap.data[j]
k = j
}
heap.data[k] = temp
}
// Show 显示堆的内容
func (heap MaxHeap) Show() {
for i, e := range heap.data {
if i == 0 {
continue
} else {
fmt.Println(e)
}
}
}
