5 基本数据结构：堆

什么是堆

堆是一种经过排序的树形数据结构，每个节点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根节点的值最小（或最大），且根节点的两个子树也是一个堆。

最大堆和最小堆.jpg

由于堆的这个特性，所有常用来实现优先队列。堆的存取是随意的，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出自己想要的书。

堆的性质:

堆中的某个节点的值总是不大于或不小于其父节点的值(大于还是小于父亲节点,就要看建立的是什么堆了)
本质上，堆的存储结构就是用数组实现的完全二叉树。

完全二叉树：只有最下面的两层节点度小于2，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树。

数学定义：

如果有一个集合K= {k0,k1,k2,k3,k4,k5,kn-1},把他的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中,并满足:
K1<=K2i+1且Ki<=K2i+2 (i = 0,1,2,)则成为小堆 ,那么反之如果 K1>= K2i+1且Ki>=K2i+2 就是大堆。

堆和二叉搜索树的区别

• 节点的顺序：在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

• 内存占用：二叉搜索树占用的内存空间比堆存储的数据要多。因为二叉搜索树必须为节点对象以及左/右子节点指针分配内存，而堆仅仅使用一个数组来存储数据，且不使用指针。

• 平衡：二叉搜索树必须是在“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

• 搜索：在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

Go 实现堆数据结构

container/heap标准包提供了对任意类型（实现了heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树。
树的最小元素为其根元素，索引0的位置。

关于container/heap包：
任何实现了本接口的类型都可以用于构建最小堆:

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

最小堆可以通过heap.Init建立，数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是：

 !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

注意接口的Push和Pop方法是供heap包调用的，请使用heap.Push和heap.Pop来向一个堆添加或者删除元素。

以下实现一个简单的数组切片结构，让它实现heap.Interface接口：

// 定义一个正方形的结构体存储元素，它作为堆元素
type Rectangle struct {
    width  int
    height int
}

// 简单计算面积
func (rec *Rectangle) Area() int {
    return rec.width * rec.width
}

// 定义一个数组切片类型，作为堆的存储载体，实现container/heap接口，自动构建堆
type RectHeap []Rectangle

// 实现heap.Interface接口
func (rec RectHeap) Len() int {
    return len(rec)
}

// 实现sort.Iterface
func (rec RectHeap) Swap(i, j int) {
    rec[i], rec[j] = rec[j], rec[i]
}
// 最小堆排序方式
func (rec RectHeap) Less(i, j int) bool {
    return rec[i].Area() < rec[j].Area()
}

// 实现heap.Interface接口定义的方法
func (rec *RectHeap) Push(h interface{}) {
    *rec = append(*rec, h.(Rectangle))
}
func (rec *RectHeap) Pop() (x interface{}) {
    n := len(*rec)
    x = (*rec)[n-1]      // 返回删除的元素
    *rec = (*rec)[:n-1] // [n:m]不包括下标为m的元素
    return x
}

测试运行：

// 初始化一个数组
    hp := &RectHeap{}
    *hp = append(*hp, Rectangle{3, 3})
    *hp = append(*hp, Rectangle{2, 2})
    *hp = append(*hp, Rectangle{4, 4})
    *hp = append(*hp, Rectangle{8, 8})
    *hp = append(*hp, Rectangle{5, 5})

    // 打印数组
    fmt.Println("打印原切片: ", hp)

    // 堆初始化，构建了一个堆结构,再打印
    heap.Init(hp)
    fmt.Println("打印构建堆后的数组: ", hp)
    // 推入一个最最小的新元素进堆
    fmt.Println("推入一个元素入堆: {10,10}")
    heap.Push(hp, Rectangle{10, 10})
    // 弹出最小堆的堆顶
    fmt.Println("弹出最小堆的堆顶：", heap.Pop(hp))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)


    // 弹出最小堆的堆顶
    fmt.Println("弹出最小堆的堆顶：", heap.Pop(hp))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)

    // 弹出最小堆的堆顶
    fmt.Println("弹出最小堆的堆顶：", heap.Pop(hp))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)

    fmt.Println("移除第二个元素：", heap.Remove(hp,1))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)

    // 弹出最小堆的堆顶
    fmt.Println("弹出最小堆的堆顶：", heap.Pop(hp))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)

    // 弹出最小堆的堆顶
    fmt.Println("弹出最小堆的堆顶：", heap.Pop(hp))
    // 打印重构后的堆
    fmt.Println("打印重构后的堆: ", hp)

输出结果：

打印原切片:  &[{3 3} {2 2} {4 4} {8 8} {5 5}]
打印构建堆后的数组:  &[{2 2} {3 3} {4 4} {8 8} {5 5}]
推入一个元素入堆: {10,10}
弹出最小堆的堆顶： {2 2}
打印重构后的堆:  &[{3 3} {5 5} {4 4} {8 8} {10 10}]
弹出最小堆的堆顶： {3 3}
打印重构后的堆:  &[{4 4} {5 5} {10 10} {8 8}]
弹出最小堆的堆顶： {4 4}
打印重构后的堆:  &[{5 5} {8 8} {10 10}]
移除第二个元素： {8 8}
打印重构后的堆:  &[{5 5} {10 10}]
弹出最小堆的堆顶： {5 5}
打印重构后的堆:  &[{10 10}]
弹出最小堆的堆顶： {10 10}
打印重构后的堆:  &[]

heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。