文章目錄
- 一、優先隊列的基本概念？
- 二、一些簡單的實作
- 三、二叉堆
-
- 3.1 二叉堆簡介
- 3.2 二叉堆的兩種性質
-
-
- 3.2.1 結構性質：
- 3.2.2 堆序性質：
-
- 3.3 二叉堆的基本操作
-
-
- 3.3.1 插入（insert）：
- 3.3.2 删除最小元(deleteMin)：
- 3.3.3 其他堆操作：
-
- 四、d-堆（簡單了解）
- 五、左式堆
-
- 5.1 左式堆簡介
- 5.2 左式堆基本操作
- 六、斜堆
-
- 6.1 左式堆基本操作
- 七、二項隊列
-
- 7.1 二項隊列的結構
- 7.2 二項隊列的操作
- 7.2 二項隊列的實作
- 八、标準庫中的優先隊列
一、優先隊列的基本概念？
優先隊列是一種應該滿足一下兩種操作的資料結構：
1.插入（insert）,顯然這是往隊列中存放元素的
2.删除最小者，展現出優先。
優先隊列應用的簡單舉例：
1.作業系統的任務排程
2.排序（見第七章，即下周分享的内容）
3.用于貪婪算法（見第十章）的實作，該算法通過反複求出最小元來進行操作。
二、一些簡單的實作
有幾種明顯的方法可以實作優先隊列：
1.使用一個簡單的連結清單，在表頭以O（1）執行插入操作，并周遊該連結清單以O（N）删除最小元。
2.讓連結清單保持排序狀态，這樣插入将是O(N)。
請思考對于一個隊列來說，是使用1更好還是2更好。
3.使用二叉查查找樹（左節點<根節點<右節點）。這樣兩種操作的平均時間複雜度都為O（logN），具體受樹的深度（平衡度）影響。如果使用平衡二叉樹，會保持樹的平衡，但是維持樹的平衡也需要相應時間。但是隊列中不需要連結清單這種結構，下面來看看二叉查找樹如何和隊列合并。
三、二叉堆
3.1 二叉堆簡介
我們将要使用的這種資料結構叫作二叉堆，它的使用對于優先隊列的實作相當普遍，以至于當堆這個次不加修飾的用在優先隊列的上下文時，一般都是指這種資料結構。類似于二叉查找樹一樣，對也有兩個性質—1.結構性，2.堆序性。和AVL樹類似，對堆的一次操作可能破環這兩個性質中的一個，是以，堆的操作必須到堆的所有性質都被滿足才能被終止。
3.2 二叉堆的兩種性質
3.2.1 結構性質：
堆是一棵被完全填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入。這樣的樹稱為完全二叉樹。完全二叉樹的高度為logN。完全二叉樹十分規律是以可以使用數組表示，而不需要使用鍊。
完全二叉樹與完滿二叉樹與AVL樹 https://blog.csdn.net/weixin_38371369/article/details/109296260
對于任意位置i上的元素，其左兒子在2i的位置上，右兒子在2i+1的位置上。是以不需要連結清單，并且周遊操作極其簡單。圖中堆大小的界限為13個元素，該數組有一個位置0，後面将詳細叙述。
3.2.2 堆序性質：
在一個堆中，對于每一個節點X，X的父親中的關鍵字小于（或等于）X中的關鍵字。
為什麼如此定義？
堆的主要操作為插入和找出最小元素，為保證快速（以O（1））找出最小元素是以最小元素應該在根上。但是保持堆序性和結構性，需要O（logN）。
3.3 二叉堆的基本操作
3.3.1 插入（insert）：
使用一種叫上濾的政策，建立空穴，并找到元素應該插入的位置，如下圖所示
為什麼建立空穴？
保持二叉堆的結構性質----完全樹。
3.3.2 删除最小元(deleteMin)：
使用下濾政策，類似于上濾政策。删除最小元後，最後一個元素的位置一定會變動（保持結構性質），是以删除最小元後的主要操作是為最後一個元素找到應該存在的位置，如下圖：
3.3.3 其他堆操作：
1.decreasrKey(降低關鍵字的值)
在某一個節點上将值降低，降低值可能破壞堆序性，需要上濾進行調整
2.increaseKey(增加關鍵字的值)
在某一個節點上增加值，需要下濾進行調整
3.delete(删除)
此操作通過先執行decreaseKey,然後再執行deleteMin。
4.buildHeap（建構堆）
一般的算法是将N項以任意順序放入樹種，保持結構性。之後通過對每個節點（從下往上）下濾來完成堆序性的維持。
四、d-堆（簡單了解）
d-堆就是二叉堆，隻不過2變成了d。比如4-堆。
思考d-堆和二叉堆相比的優缺點
隊列太大的時候可以表現出b-tree的效果。插入時間減少為O(logdN)。删除最小項變得複雜，比較次數表多
五、左式堆
5.1 左式堆簡介
左式堆也具有堆序性和結構性，其堆序性同其他堆。結構性上有所不同。對于左式堆的基本操作時間複雜度都為O（logN）
左式堆的結構性質：對于堆中的每一個節點X，做兒子的零路徑長至少于右兒子的零路徑長相等。
零路徑長：任一節點X的零路徑長（null path length）npl定義為X到一個不具有兩個兒子的節點的最短路徑長。任意節點的零路徑長比它的各個兒子的零路徑長的最小值大1.空節點的零路徑長為-1.
5.2 左式堆基本操作
合并：遞歸的将最小根節點堆的右子樹與另一個堆合并。若其不符合左式堆的結構性質則調換其左右兒子。遞歸的基準情形為判斷左子樹是否為空，為空則替換，不為空則判斷右子樹為空則替換之。之後判斷是否符合左式堆的結構性，不符合則交換。最後計算零路徑長。
删除最小項:删除根節點，之後将左子樹和右子樹合并。
插入：插入節點和左式堆的合并。
六、斜堆
6.1 左式堆基本操作
斜堆是具有堆序的二叉樹，但不存在對樹結構的限制。
斜堆的合并操作和左式堆基本一緻，除了對左右兒子交換，因為斜堆沒有結構限制。斜堆的交換是無條件的，除右路徑上的所有節點的最大者不交換其左右兒子，剩下的都要交換。
七、二項隊列
7.1 二項隊列的結構
二項隊列是二項樹的集合(森林)，每一棵堆序樹都是一棵二項樹，每個高度至多存在一棵。二項樹的節點個數為2^k,其中k為二項樹的高度。高度為0的二項樹是一棵單節點樹。二項隊列的插入合并删除最小項的時間複雜度都為O（logN）
7.2 二項隊列的操作
合并：保證合并後隊列中沒有一樣高的樹，相同高度的樹合并時，以較小的根節點作為根，連接配接另一棵二項樹。
插入：與另一個隻有一棵高度為零的二項樹的二項隊列合并
删除最小項：找到最小根并删除，如删除後不滿足二項隊列結構，則合并。
7.2 二項隊列的實作
在代碼中如何表示二項隊列的這種結構？類似于hashmap。
二項隊列初始化一個數組，二項隊列中的二項樹每一個的根節點放到數組中。每一個連結清單的節點有兩個屬性，分别記錄一個兒子節點和一個兄弟節點。這樣即可完全描繪二項隊列的資料結構，如下圖。
二項隊列種二項樹合并代碼大概是這樣的,其中t1是小根的二項樹
t2.nextSibLing=t1.leftChild;
t1.leftChild = t2;
八、标準庫中的優先隊列
java1.5以前，java類庫中不存在對優先隊列的支援。1.5出現了泛型類PriorityQueue。在該類中insert、findMin、deleteMin分别通過add、element、和remove表示。