二叉堆
堆有序定义：当一颗二叉树的每个节点都大于等于它的两个子节点时， 被称为堆有序。
二叉堆定义： 二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存(不使用数组中第一个位置)。
在一个二叉堆中，位置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非常大的时候，如何利用有限的资源高效的实现是比较大的挑战。
| 示例 | 时间 | 空间 |
|---|---|---|
| 排序算法 | NlogN | N |
| 初级实现(数组/链表)的优先队列 | NM | M |
| 堆实现的优先队列 | NlogM | M |
优先队列也是很多重要算法的基础， 例如一些重要的图搜索算法、数据压缩算法等。
优先队列两个最重要的操作是：删除最大(小)元素和插入元素。使用上跟队列、栈使用比较相似，在实现上， 和栈、队列最大的不同是： 对于性能上的要求。队列和栈的实现能够在常数时间内完成所有的操作，而对于优先队列，初级实现(有序/无序的数组/链表)在删除元素和插入元素之一操作的最坏情况下需要线性时间完成，而基于二叉堆的实现能够保证这两种操作更快(对数级别)。
基于二叉堆实现的优先队列：
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函数参照上文。
多叉堆
略
参考资料: 《算法》第四版
