优先队列是允许至少两种操作的数据结构：insert(插入)，以及deleteMin(删除最小者)，它的工作是找出,返回并删除优先队列中最小的元素。insert操作等价于enqueue(入队)，而deleteMin则是队列运算dequeue(出队)在优先队列中的等价操作。
实现优先队列的一种方法是使用二叉查找树，操作的平均运行时间三O（logN）
二叉堆
堆是一颗完全被填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。
因为完全二叉树这么有规律，它可以用一个数组表示而不使用链。
对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 中，它的父亲则在位置 i/2。
因此，一个堆结构将有一个数组和一个代表当前堆的大小的整数组成。
堆序性质
让操作快速执行的性质是堆序性质。由于我们想要快速找出最小元，因此最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它的所有后裔。
堆序性质： 在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。
package heap
//AnyType 实现compareTo的int
type AnyType int
func (a AnyType) compareTo(b AnyType) int {
result := 0
if a < b {
result = -1
} else if a == b {
result = 0
} else if a > b {
result = 1
}
return result
}
// BinaryHeap 二叉堆
type BinaryHeap struct {
CurrentSize int // 二叉堆的大小
Aarray []AnyType
}
// Insert 插入
func (h *BinaryHeap) Insert(a AnyType) {
child := h.CurrentSize + 1
if child > len(h.Aarray)-1 {
array := make([]AnyType, child*2)
for i := 0; i < len(h.Aarray); i++ {
array[i] = h.Aarray[i]
}
h.Aarray = array
}
father := child / 2
for {
if father == 0 {
break
}
if a.compareTo(h.Aarray[father]) < 0 {
h.Aarray[child] = h.Aarray[father]
child = child / 2
father = father / 2
} else {
break
}
}
h.Aarray[child] = a
h.CurrentSize = h.CurrentSize + 1
}
// DeleteMin 删除最小元素
func (h *BinaryHeap) DeleteMin() AnyType {
if len(h.Aarray) == 0 {
return AnyType(-1)
}
any := h.Aarray[1]
last := h.Aarray[h.CurrentSize]
father := 1
childleft := father * 2
childRight := father*2 + 1
for {
if len(h.Aarray)-1 < childleft {
break
}
if h.Aarray[childleft] == 0 && h.Aarray[childRight] == 0 {
break
}
if len(h.Aarray)-1 >= childRight {
if h.Aarray[childleft] >= h.Aarray[childRight] {
if last <= h.Aarray[childRight] {
h.Aarray[father] = last
break
} else {
h.Aarray[father] = h.Aarray[childRight]
father = childRight
}
} else {
if last <= h.Aarray[childRight] {
h.Aarray[father] = last
break
} else {
h.Aarray[father] = h.Aarray[childleft]
father = childleft
}
}
childleft = father * 2
childRight = father*2 + 1
}
}
h.Aarray[father] = last
h.Aarray[h.CurrentSize] = 0
h.CurrentSize = h.CurrentSize - 1
return any
}
package heap
import (
"testing"
)
func Test_BinaryHeap(t *testing.T) {
binaryHeap := &BinaryHeap{
CurrentSize: 0,
Aarray: []AnyType{-1},
}
binaryHeap.Insert(AnyType(13))
binaryHeap.Insert(AnyType(14))
binaryHeap.Insert(AnyType(16))
binaryHeap.Insert(AnyType(19))
binaryHeap.Insert(AnyType(21))
binaryHeap.Insert(AnyType(19))
binaryHeap.Insert(AnyType(68))
binaryHeap.Insert(AnyType(65))
binaryHeap.Insert(AnyType(26))
binaryHeap.Insert(AnyType(32))
binaryHeap.Insert(AnyType(31))
binaryHeap.DeleteMin()
}
func Test_BinaryHeap2(t *testing.T) {
binaryHeap := &BinaryHeap{
CurrentSize: 0,
Aarray: []AnyType{-1},
}
binaryHeap.Insert(AnyType(13))
binaryHeap.Insert(AnyType(14))
binaryHeap.Insert(AnyType(16))
binaryHeap.Insert(AnyType(35))
binaryHeap.Insert(AnyType(21))
binaryHeap.Insert(AnyType(19))
binaryHeap.Insert(AnyType(68))
binaryHeap.Insert(AnyType(65))
binaryHeap.Insert(AnyType(36))
binaryHeap.Insert(AnyType(32))
binaryHeap.Insert(AnyType(31))
binaryHeap.DeleteMin()
}
其他函数
decreaseKey(降低关键字的值)
decreaseKey(p,△）操作降低在位置p处的项的值，降值的幅度为正的能量△。由于这可能破坏堆序性质，因此必须通过上滤对堆进行调整。
increaseKey(增加关键字的值)
increaseKey(p,△）操作增加在位置p处的项的值，增加的幅度为正的能量△。由于这可能破坏堆序性质，因此必须通过下滤对堆进行调整。
delete(删除)
delete(p)操作删除堆中位置p上的节点。该操作通过首先执行decreaseKep（p, ∞）然后再执行deleteMin()来完成。
buildHeap(构建堆)
有时二叉堆是由一些项的初始集合构造而得。这种构造方法以N项作为输入，并把它们放入一个堆中。显然，这可以使用N个相继的insert操作来完成。由于每个insert将花费O（1）平均时间以及O（logN）的最坏情形时间，因此该算法的总运行时间是O（N）平均时间而不是最O（NlogN）最坏情形时间。
func (h *BinaryHeap) buildHeap(array []AnyType) {
h.Aarray = make([]AnyType, len(array)+1)
for i := 0; i < len(array); i++ {
size := i + 1
h.Aarray[size] = array[i]
}
h.CurrentSize = len(array)
for i := h.CurrentSize / 2; i > 0; i-- {
h.percolateDown(i)
}
}
func (h *BinaryHeap) percolateDown(i int) {
if i >= h.CurrentSize {
return
}
for {
if i*2 <= h.CurrentSize {
if h.Aarray[i*2] <= h.Aarray[i*2+1] && h.Aarray[i] > h.Aarray[i*2] {
tmp := h.Aarray[i*2]
h.Aarray[i*2] = h.Aarray[i]
h.Aarray[i] = tmp
}
if h.Aarray[i*2] > h.Aarray[i*2+1] && h.Aarray[i] > h.Aarray[i*2+1] {
tmp := h.Aarray[i*2+1]
h.Aarray[i*2+1] = h.Aarray[i]
h.Aarray[i] = tmp
}
i = i / 2
}
break
}
}
二叉堆的应用场景
选择问题
输入N个元素以及一个整数k,找出第k个最大的元素。
解决：将N个元素读入一个数组。然后对该数组应该buildHeap算法。最后，执行k次delteMin操作，从该堆最前提取的元素就是我们的元素。---->堆排序（heapsort）TODO
d-堆
d-堆是二叉堆的简单推广，它就像一个二叉堆，只是所有的节点都有d个儿子（因此，二叉堆是2-堆）。
d-堆要比二叉堆浅得多，它将insert操作的运行时间改为O（logᵈN）。然而，对于大的d，deleteMin操作费时得多，虽然树是浅了，但是d个儿子中的最小者是必须要找出的，如使用标准的算法，这会花费d-1次比较，于是将操作的用时提高到O（d logᵈN）。
二项队列
二项队列支持所有这三种操作（merge + insert + deleteMin）， 每次操作的最坏情形运行时间为O（logN）， 而插入操作平均花费常数时间；
二项队列与优先队列的区别：一个二项队列不是一颗堆序的树，而是堆序的树的集合，称为森林。每一科堆序树都是用约束的形式，叫做二项树。
从图中看到，二项树Bₖ由一个带有儿子B₀，B₁ ....Bₖ-₁的根组成。高度为k的二项树恰好有2ᵏ 个节点。
二项队列与二叉堆的比较
| 基本操作： | insert(平均情况下) | deleteMin | merge |
|---|---|---|---|
| 二项队列： | O(1) | O(logN) | O(logN) |
| 二叉堆： | O(1) | O(logN) | O(N) |
可见，二项队列有效地支持了merge操作。
但是，需要注意的是：二项队列的实现用到了链表，树中的每个元素存储在一个结点中，结点之间采用“左孩子右兄弟”表示法进行链接，此外还需要一个额外的数组来保存各棵二项树的根结点，存储开销要比二叉堆大。
而对于二叉堆的存储，则简单得多。它只需要一个一维数组即可存储各个元素。
