實現(xiàn)優(yōu)先隊列結(jié)構(gòu)主要是通過堆完成，主要有：二叉堆、d堆、左式堆、斜堆、二項堆、斐波那契堆、pairing 堆等。

?

1. 二叉堆

?

1.1. 定義

完全二叉樹，根最小。

存儲時使用層序。

?

1.2. 操作

(1). insert（上濾）

插入末尾 26，不斷向上比較，大于26則交換位置，小于則停止。

?

(2). deleteMin（下濾）

提取末尾元素，放在堆頂，不斷下濾：

?

(3). 其他操作：

都是基于insert（上濾）與deleteMin（下濾）的操作。

減小元素：減小節(jié)點的值，上濾調(diào)整堆。

增大元素：增加節(jié)點的值，下濾調(diào)整堆。

刪除非頂點節(jié)點：直接刪除會出問題。方法：減小元素的值到無窮小，上濾后刪除。

Merge：insert>?

2. d叉堆

2.1. 定義

完全d叉樹，根最小。

存儲時使用層序。

?

2.2. 操作:

操作跟二叉堆基本一致：insert,deleteMin,增大元素，減小元素，刪除非頂元素，merge。

?

2.3 二叉堆與d叉堆的對比：

?

3. 左式堆

3.1. 定義

零路徑長度：到?jīng)]有兩個兒子的節(jié)點最短距離左式堆：1.一棵二叉樹2.零路徑長：左兒子≧右兒子，父節(jié)點= min{兒子} +1（這條性質(zhì)導(dǎo)致了左式堆的嚴(yán)重左偏）?零路徑長度： ??

3.2. 操作:

(1) merge :

原則:根值大的堆與根值小的堆的右子堆合并(根值：根位置的元素值，并非零路徑長度)? ?具體分三種情況（設(shè)堆H1的根值小于H2）H1只有一個節(jié)點H1根無右孩子H1根有右孩子?(1.1).H1只有一個節(jié)點，若出現(xiàn)不滿足：零路徑長：左兒子≧右兒子，交換左右孩子。 ?(1.2).H1根無右孩子，若出現(xiàn)不滿足：零路徑長：左兒子≧右兒子，交換左右孩子。?

?

(1.3).H1根有右孩子

1.初始狀態(tài)，H1的根6，H2的根為8，將H2合并到H1。

2.將H1構(gòu)造成根無右孩子的形式：

3.將元素10, merge到H2，要首先將H2構(gòu)造成根無右孩子的形式，遞歸，merge，若出現(xiàn)不滿足：零路徑長：左兒子≧右兒子，交換左右孩子……

——》——》——》

4.

5.

3.3. 性質(zhì)分析:

insert：mergedeleteMin：delete? root，merge時間復(fù)雜度：merge與右路徑長度之和成正比；最壞O(logN)缺點：交換需判斷；維護(hù)零路徑長

?

4. 斜堆

?

4.1. 定義

二叉樹，根最小。由此可見：? ??特點：merge無條件交換。?時間復(fù)雜度：最壞O(N)；最好?(1)；平均O(logN)

?

4.2性能比較：

?

?

5. 總結(jié)

?

如果是不支持所謂的合并操作union的話，普通的堆數(shù)據(jù)結(jié)構(gòu)就是一種很理想的數(shù)據(jù)結(jié)構(gòu)（堆排序）。 但是如果想要支持集合上的合并操作的話，最好是使用二項堆或者是斐波那契堆，普通的堆在union操作上最差的情況是O(n)，但是二項堆和斐波那契堆是O(lgn)。

???????????????????????? Binary heap??????????????Binomial heap????????? Fibonacci heap

?????????????????????? 二叉堆（最壞情況） 二項堆（最壞情況）（斐波那契堆（平攤））

Procedure (worst-case) (worst-case) (amortized) -------------------------------------------------------------- MAKE-HEAP (1) (1) (1) INSERT (lg n) O(lg n) (1) MINIMUM (1) O(lg n) (l) EXTRACT-MIN (lg n) (1g n) O(lg n) UNION (n) O(lg n) (1) DECREASE-KEY (lg n) (lg n) (1) DELETE (1g n) (lg n) O(lg n)

總結(jié)

以上是生活随笔為你收集整理的结构之美——优先队列基本结构（四）——二叉堆、d堆、左式堆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。