堆

二叉堆是一棵满二叉树，父节点的值大于子节点。

用数组存储二叉堆，假如一个节点的下标为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)
        }
    }
}