数据结构与算法分析 chapter06 -优先队列（堆）

 优先队列是允许至少两种操作的数据结构：insert(插入)，以及deleteMin(删除最小者)，它的工作是找出,返回并删除优先队列中最小的元素。insert操作等价于enqueue(入队)，而deleteMin则是队列运算dequeue(出队)在优先队列中的等价操作。
 实现优先队列的一种方法是使用二叉查找树，操作的平均运行时间三O（logN）

二叉堆

 堆是一颗完全被填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。

完全二叉树.png

 因为完全二叉树这么有规律，它可以用一个数组表示而不使用链。

完全二叉树的数组实现.png

 对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 中，它的父亲则在位置 i/2。

 因此，一个堆结构将有一个数组和一个代表当前堆的大小的整数组成。

堆序性质

 让操作快速执行的性质是堆序性质。由于我们想要快速找出最小元，因此最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它的所有后裔。
堆序性质： 在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。

image.png insert.png deleteMin.png

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-堆）。

3-堆.png

d-堆要比二叉堆浅得多，它将insert操作的运行时间改为O（logᵈN）。然而，对于大的d，deleteMin操作费时得多，虽然树是浅了，但是d个儿子中的最小者是必须要找出的，如使用标准的算法，这会花费d-1次比较，于是将操作的用时提高到O（d logᵈN）。

image.png

二项队列

  二项队列支持所有这三种操作（merge + insert + deleteMin）， 每次操作的最坏情形运行时间为O（logN）， 而插入操作平均花费常数时间；

 二项队列与优先队列的区别：一个二项队列不是一颗堆序的树，而是堆序的树的集合，称为森林。每一科堆序树都是用约束的形式，叫做二项树。

二项树.png

 从图中看到，二项树Bₖ由一个带有儿子B₀，B₁ ....Bₖ-₁的根组成。高度为k的二项树恰好有2ᵏ 个节点。

image.png image.png

二项队列与二叉堆的比较

基本操作：	insert(平均情况下)	deleteMin	merge
二项队列：	O(1)	O(logN)	O(logN)
二叉堆：	O(1)	O(logN)	O(N)

可见，二项队列有效地支持了merge操作。

但是，需要注意的是：二项队列的实现用到了链表，树中的每个元素存储在一个结点中，结点之间采用“左孩子右兄弟”表示法进行链接，此外还需要一个额外的数组来保存各棵二项树的根结点，存储开销要比二叉堆大。

而对于二叉堆的存储，则简单得多。它只需要一个一维数组即可存储各个元素。