基于二叉堆的优先队列和堆排序(golang实现)

二叉堆

堆有序定义：当一颗二叉树的每个节点都大于等于它的两个子节点时， 被称为堆有序。
二叉堆定义： 二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存(不使用数组中第一个位置)。
在一个二叉堆中，位置k的节点的父节点位置为|k/2|(k/2向下取整)，两个子节点的位置分别为：2k、2k+1。
下文中二叉堆简称为堆。
堆的有序化定义：堆的操作会首先进行一些改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。
在有序化的过程中， 会遇到两种情况：
1、 当某个节点的优先级上升(或者堆底加入新元素)，需要由下至上恢复堆的顺序。 算法实现如下:

 func swim(k int) {
    for k>1&&less(k/2, k) {
        exch(k/2, k)
        k /= 2
    }
}

2、 当某个节点的优先级下降(例如， 将根节点替换为一个较小的元素)时， 需要由上至下恢复堆的顺序。
算法实现如下：

func sink(k int) {
    for 2*k <= N {  //N为二叉堆的元素数量
        j := 2*k
        if 2*k<N && less(j, j+1) {
            j += 1
        }
        if less(j, k) {
            break
        }
        exch(k, j)
        k = j
    }
}

算法使用的exch、less方法：

func less(source []int, i, j int) {
    return source[i] < source[j]
}

func exch(source []int, i, j int) {
    source[i], source[j] = source[j], source[i]
    return
}

优先队列

优先队列使用场景很多， 例如：处理很多程序中优先级最高的程序；收集一些数据，处理当前最大/最小的元素，再收集一些数据，再处理当前最大/最小的数据等等。
这些使用场景可以抽象为从N个输入元素中找到最大/最小的M个元素。可以看一下下面表格中一些方法实现这种需求需要的资源，特别是在N非常大的时候，如何利用有限的资源高效的实现是比较大的挑战。

优先队列也是很多重要算法的基础， 例如一些重要的图搜索算法、数据压缩算法等。
优先队列两个最重要的操作是：删除最大(小)元素和插入元素。使用上跟队列、栈使用比较相似，在实现上， 和栈、队列最大的不同是： 对于性能上的要求。队列和栈的实现能够在常数时间内完成所有的操作，而对于优先队列，初级实现(有序/无序的数组/链表)在删除元素和插入元素之一操作的最坏情况下需要线性时间完成，而基于二叉堆的实现能够保证这两种操作更快(对数级别)。

基于二叉堆实现的优先队列：
1、 插入操作：
将新元素插入到数组的尾部，增加堆的大小并让这个元素swim(对应上面二叉堆的优先级上升操作)到相应的位置。
2、 删除操作：
从数组顶端删除最大的元素，并将数组中最后一个元素放置到顶端，减小堆的大小， 并让这个元素sink(对应上面二叉堆的优先级下降操作)到响应的位置
具体实现代码：

type MaxPQ struct {
    source []int
    s int
}

func NewMaxPQ(k int) *MaxPQ {
    return &MaxPQ{
        source: make([]int, k+1),
        s: 0,
    }
}

func (q *MaxPQ) insert(key int) { //插入操作
    q.s++
    q.source[q.s] = key
    q.swim(q.s)
}

func (q *MaxPQ) delMax() (x int) { //删除操作
    x = q.source[1]
    q.exch(1, q.s)
    q.s--
    q.sink(1)
    return 
}

func (q *MaxPQ) swim(k int) {
    for k>1&&q.less(k/2, k) {
        q.exch(k/2, k)
        k /= 2
    }
}

func (q *MaxPQ) sink(k int) {
    for 2*k <= q.s {
        j := 2*k
        if j<q.s&&q.less(j, j+1) {
            j += 1
        }
        if !q.less(k, j) {
            break
        }
        q.exch(k, j)
        k = j
    }
}

func (q *MaxPQ) isEmpty() bool {  
    return q.s == 0
}

func (q *MaxPQ) size() int {
    return q.s
}

func (q *MaxPQ) less(i, j int) bool {
    return q.source[i] < q.source[j]
}

func (q *MaxPQ) exch(i, j int) {
    q.source[i], q.source[j] = q.source[j], q.source[i]
}

func (q *MaxPQ) show() {
    var (
        i = 0
    )
    for i<=q.s {
        fmt.Fprintf(os.Stdout, "%v ", q.source[i])
        i++
    }
    fmt.Println()
}

索引优先队列

索引优先队列在多向归并的使用场景中非常有效， 例如：从多个有序的输入流归并成一个有序序列，如果有足够的空间，你可以简单的把它们读入一个数组并排序，但如果使用了优先队列，无论输入有多长你都可以把他们全部读入并排序。
索引优先队列的实现如下：

type IndexMinPQ struct {
    keys []int //元素存放的数组
    pq []int //二叉堆实现的索引
    qp []int //索引二叉堆的逆序, 可以很方便的做contains判断
    N int //PQ中元素的数量
}
func NewIndexMinPQ(max int) (imq *IndexMinPQ) {
    imq = &IndexMinPQ{
        keys: make([]int, max+1),
        pq: make([]int, max+1),
        qp: make([]int, max+1),
    }
    for i:=0; i<=max; i++ {
        imq.qp[i] = -1  //初始化为-1
    }
    return
}

func (imq *IndexMinPQ) insert(k int, key int) { //插入操作
    imq.N++
    imq.pq[imq.N] = k
    imq.keys[k] = key
    imq.qp[k] = imq.N
    imq.swim(imq.N)
}

func (imq *IndexMinPQ) delMin() (indexOfMin int) {  //删除操作
    indexOfMin = imq.keys[imq.pq[1]]
    imq.exch(1, imq.N)
    imq.N--
    imq.sink(1)
    imq.keys[imq.pq[imq.N+1]] = -1
    imq.qp[imq.pq[imq.N+1]] = -1
    return
}

func (imq *IndexMinPQ) swim(k int) { 
    for k>1 && (!imq.less(k/2, k)) {
        imq.exch(k/2, k)
        k /= 2
    }
}

func (imq *IndexMinPQ) sink(k int) {  
    for 2*k <= imq.N {
        j := 2*k
        if 2*k<imq.N && imq.less(j+1, j) {
            j += 1
        }
        if imq.less(k, j) {
            break
        }
        imq.exch(k, j)
        k = j
    }
}

func (imq *IndexMinPQ) less(i, j int) bool {
    return imq.keys[imq.pq[i]] < imq.keys[imq.pq[j]]
}

func (imq *IndexMinPQ) exch(i, j int) {
    imq.pq[i], imq.pq[j] = imq.pq[j], imq.pq[i]
    imq.qp[imq.pq[i]], imq.qp[imq.pq[j]] = imq.qp[imq.pq[j]], imq.qp[imq.pq[i]]
}

func (imq *IndexMinPQ) show() {
    for i:=1; i<=imq.N; i++ {
        fmt.Printf("%v ", imq.keys[imq.pq[i]])
    }
    fmt.Println()
}

func (imq *IndexMinPQ) min() int {
    return imq.keys[imq.pq[1]]
}

func (imq *IndexMinPQ) contains(k int) bool {
    return imq.qp[k] != -1
}

堆排序

有了上面优先队列的例子， 再看堆排序就很简单了。
堆排序算法分为两阶段：在堆的构造阶段，将原始数组重新组织到一个堆中，然后在下沉阶段，从堆中按递减顺序取出所有元素并得到排序结果。
在堆的构造阶段，可以从左到右遍历数组，用swim()保证扫描到的位置左侧都是一颗堆有序的完全树，但更高效的方法是：从右至左用sink()函数构造子堆，开始时我们只需要扫描一半的元素，因为我们可以跳过大小为1的子堆。

func heapSort(source []int) {
    var (
        l = len(source)-1
        j = l
    )
    for i:=l/2; i>=1; i-- {  //构造堆阶段，只需要扫描一半的元素
        sink(source, i, l)
    }
    for j>1 {   //下沉阶段
        exch(source, 1, j)
        j--
        sink(source, 1, j)
    }
}

func sink(source []int, i, length int) {
    for 2*i<=length {
        x := 2*i
        if x<length&&less(source, x, x+1) {
            x += 1
        }
        if !less(source, i, x) {
            break
        }
        exch(source, i, x)
        i *= 2
    }
}

less函数和exch函数参照上文。

多叉堆

略

参考资料: 《算法》第四版