?優(yōu)先隊(duì)列是允許至少兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert(插入)，以及deleteMin(刪除最小者)，它的工作是找出,返回并刪除優(yōu)先隊(duì)列中最小的元素。insert操作等價(jià)于enqueue(入隊(duì))，而deleteMin則是隊(duì)列運(yùn)算dequeue(出隊(duì))在優(yōu)先隊(duì)列中的等價(jià)操作。
?實(shí)現(xiàn)優(yōu)先隊(duì)列的一種方法是使用二叉查找樹，操作的平均運(yùn)行時(shí)間三O（logN）
二叉堆
?堆是一顆完全被填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入。這樣的樹稱為完全二叉樹。
?因?yàn)橥耆鏄溥@么有規(guī)律，它可以用一個(gè)數(shù)組表示而不使用鏈。
?對于數(shù)組中任一位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子后的單元 (2i+1) 中，它的父親則在位置 i/2。
?因此，一個(gè)堆結(jié)構(gòu)將有一個(gè)數(shù)組和一個(gè)代表當(dāng)前堆的大小的整數(shù)組成。
堆序性質(zhì)
?讓操作快速執(zhí)行的性質(zhì)是堆序性質(zhì)。由于我們想要快速找出最小元，因此最小元應(yīng)該在根上。如果我們考慮任意子樹也應(yīng)該是一個(gè)堆，那么任意節(jié)點(diǎn)就應(yīng)該小于它的所有后裔。
堆序性質(zhì)： 在一個(gè)堆中，對于每一個(gè)節(jié)點(diǎn)X，X的父親中的關(guān)鍵字小于（或等于）X中的關(guān)鍵字，根節(jié)點(diǎn)除外（它沒有父親）。
package heap
//AnyType 實(shí)現(xiàn)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()
}
其他函數(shù)
decreaseKey(降低關(guān)鍵字的值)
?decreaseKey(p,△）操作降低在位置p處的項(xiàng)的值，降值的幅度為正的能量△。由于這可能破壞堆序性質(zhì)，因此必須通過上濾對堆進(jìn)行調(diào)整。
increaseKey(增加關(guān)鍵字的值)
?increaseKey(p,△）操作增加在位置p處的項(xiàng)的值，增加的幅度為正的能量△。由于這可能破壞堆序性質(zhì)，因此必須通過下濾對堆進(jìn)行調(diào)整。
delete(刪除)
?delete(p)操作刪除堆中位置p上的節(jié)點(diǎn)。該操作通過首先執(zhí)行decreaseKep（p, ∞）然后再執(zhí)行deleteMin()來完成。
buildHeap(構(gòu)建堆)
?有時(shí)二叉堆是由一些項(xiàng)的初始集合構(gòu)造而得。這種構(gòu)造方法以N項(xiàng)作為輸入，并把它們放入一個(gè)堆中。顯然，這可以使用N個(gè)相繼的insert操作來完成。由于每個(gè)insert將花費(fèi)O（1）平均時(shí)間以及O（logN）的最壞情形時(shí)間，因此該算法的總運(yùn)行時(shí)間是O（N）平均時(shí)間而不是最O（NlogN）最壞情形時(shí)間。
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
}
}
二叉堆的應(yīng)用場景
選擇問題
? 輸入N個(gè)元素以及一個(gè)整數(shù)k,找出第k個(gè)最大的元素。
解決：將N個(gè)元素讀入一個(gè)數(shù)組。然后對該數(shù)組應(yīng)該buildHeap算法。最后，執(zhí)行k次delteMin操作，從該堆最前提取的元素就是我們的元素。---->堆排序（heapsort）TODO
d-堆
?d-堆是二叉堆的簡單推廣，它就像一個(gè)二叉堆，只是所有的節(jié)點(diǎn)都有d個(gè)兒子（因此，二叉堆是2-堆）。
d-堆要比二叉堆淺得多，它將insert操作的運(yùn)行時(shí)間改為O（log?N）。然而，對于大的d，deleteMin操作費(fèi)時(shí)得多，雖然樹是淺了，但是d個(gè)兒子中的最小者是必須要找出的，如使用標(biāo)準(zhǔn)的算法，這會花費(fèi)d-1次比較，于是將操作的用時(shí)提高到O（d log?N）。
二項(xiàng)隊(duì)列
? 二項(xiàng)隊(duì)列支持所有這三種操作（merge + insert + deleteMin）， 每次操作的最壞情形運(yùn)行時(shí)間為O（logN）， 而插入操作平均花費(fèi)常數(shù)時(shí)間；
?二項(xiàng)隊(duì)列與優(yōu)先隊(duì)列的區(qū)別：一個(gè)二項(xiàng)隊(duì)列不是一顆堆序的樹，而是堆序的樹的集合，稱為森林。每一科堆序樹都是用約束的形式，叫做二項(xiàng)樹。
?從圖中看到，二項(xiàng)樹B?由一個(gè)帶有兒子B?，B? ....B?-?的根組成。高度為k的二項(xiàng)樹恰好有2? 個(gè)節(jié)點(diǎn)。
二項(xiàng)隊(duì)列與二叉堆的比較
| 基本操作： | insert(平均情況下) | deleteMin | merge |
|---|---|---|---|
| 二項(xiàng)隊(duì)列： | O(1) | O(logN) | O(logN) |
| 二叉堆： | O(1) | O(logN) | O(N) |
可見，二項(xiàng)隊(duì)列有效地支持了merge操作。
但是，需要注意的是：二項(xiàng)隊(duì)列的實(shí)現(xiàn)用到了鏈表，樹中的每個(gè)元素存儲在一個(gè)結(jié)點(diǎn)中，結(jié)點(diǎn)之間采用“左孩子右兄弟”表示法進(jìn)行鏈接，此外還需要一個(gè)額外的數(shù)組來保存各棵二項(xiàng)樹的根結(jié)點(diǎn)，存儲開銷要比二叉堆大。
而對于二叉堆的存儲，則簡單得多。它只需要一個(gè)一維數(shù)組即可存儲各個(gè)元素。
