- 優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)支持兩種操作：刪除最大元素和插入元素
- 優(yōu)先隊(duì)列的使用和隊(duì)列（刪除最老的元素）以及棧（刪除最新的元素）類似
- 通過插入一列元素然后一個(gè)個(gè)地刪除其中最小的元素惠拭，可以用優(yōu)先隊(duì)列實(shí)現(xiàn)排序算法。一種
名為堆排序的重要排序算法也來自于基于堆的優(yōu)先隊(duì)列的實(shí)現(xiàn)
API
優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型尉共，他表示了一組值和對這些值得操作。優(yōu)先隊(duì)列最重要的操作就是刪除最大元素和插入元素乾戏。
- 刪除最大元素的方法名為 del_max()
- 插入元素的方法名為 insert()
（MinPQ模暗，和MaxPQ類似，只是含有一個(gè) del_min() 方法來刪除并返回隊(duì)列中健值最小的那個(gè)元素欧啤，只需要改變下 less() 比較的方向即可）
優(yōu)先隊(duì)列的應(yīng)用場景
輸入 N 個(gè)字符串睛藻，每個(gè)字符串都應(yīng)著一個(gè)整數(shù)，任務(wù)就是找出最大的（或是最小的）M 個(gè)整數(shù)（以其關(guān)聯(lián)的字符串）邢隧。在某些應(yīng)用場景中店印，輸入量可能非常巨大，甚至可以認(rèn)為輸入是無限的倒慧。
- 一種方法是輸入排序然后從中找出 M 個(gè)最大的元素按摘。
- 另一種方法是將每個(gè)新的輸入和已知的 M 個(gè)最大元素比較，但除非 M 較小纫谅，否則這種比較的代價(jià)會非常高昂炫贤。
只要我們能夠高效地實(shí)現(xiàn) insert() 和 del_min()，調(diào)用了 MinPQ 的 TopM 就能使用優(yōu)先隊(duì)列解決這個(gè)問題付秕。
構(gòu)造一個(gè)用數(shù)字作為鍵的優(yōu)先隊(duì)列兰珍。當(dāng)優(yōu)先隊(duì)列的大小超過 M 時(shí)就刪掉其中最小的元素。處理完所有數(shù)據(jù)盹牧，有些隊(duì)列中存放這一增序排列的最大的 M 個(gè)元素俩垃。
初級實(shí)現(xiàn)
可以使用無序（數(shù)組）或是有序（數(shù)組 / 鏈表）的方法來實(shí)現(xiàn)優(yōu)先隊(duì)列。
使用無需序列是解決這個(gè)問題的惰性方法汰寓，我們僅在必要的時(shí)候才會采取行動(dòng)口柳；使用有序序列則是解決問題的積極方法，因?yàn)槲覀儠M可能未雨綢繆有滑，是后續(xù)操作更高效跃闹。
堆的定義
數(shù)據(jù)結(jié)構(gòu)二叉堆能夠很好地實(shí)現(xiàn)優(yōu)先隊(duì)列的基本操作。在二叉堆的數(shù)組中，每個(gè)元素都要保證大于等于另兩個(gè)特定位置的元素望艺。相應(yīng)地苛秕，在堆有序的二叉樹中，每個(gè)結(jié)點(diǎn)都小于等于它的父結(jié)點(diǎn)找默。
當(dāng)一顆二叉樹的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子結(jié)點(diǎn)時(shí)艇劫，它被稱為堆有序。
二叉堆表示法
完全二叉樹只用數(shù)組而不需要指針就可以表示惩激。具體方法就是將二叉樹的結(jié)點(diǎn)按照層級順序放入數(shù)組中店煞，根結(jié)點(diǎn)在位置 1，它的子結(jié)點(diǎn)在位置2风钻，3顷蟀，而子結(jié)點(diǎn)的子結(jié)點(diǎn)則分別在位置4，5骡技，6鸣个，7...
二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按照層級儲存（不使用數(shù)組的第一個(gè)位置）布朦。
在一個(gè)堆中囤萤，位置 k 的結(jié)點(diǎn)的父結(jié)點(diǎn)的位置為 [k/2]，而它的兩個(gè)子結(jié)點(diǎn)的位置則分別為 2k是趴，2k + 1阁将。（這樣在不使用指針的情況下，我們也可以通過計(jì)算數(shù)組的索引在樹中上下移動(dòng)右遭。）
用數(shù)組（堆）實(shí)現(xiàn)的完全二叉樹的結(jié)構(gòu)是很嚴(yán)格的，但它的靈活性已經(jīng)足以讓我們高效地實(shí)現(xiàn)優(yōu)先隊(duì)列缤削。用它們我們將能實(shí)現(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作窘哈。利用在數(shù)組中無需指針即可沿樹上下移動(dòng)的便利和以下性質(zhì)，算法保證了對數(shù)復(fù)雜度的性能亭敢。
一個(gè)大小為 N 的完全二叉樹的高度為 [lgN]
堆的算法
用長度為 N+1 的數(shù)組 pq[] 來表示一個(gè)大小為 N 的堆滚婉，不使用 pq[0]，堆元素放在pq[1] 至 pq[N] 中帅刀。
堆的操作會首先進(jìn)行一些簡單的改動(dòng)让腹，打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)扣溺。這個(gè)過程叫做堆的有序化 reheapifying骇窍。
在有序化的過程中，會遇到兩種情況：
- 某個(gè)結(jié)點(diǎn)的優(yōu)先級上升（或是在堆底加入一個(gè)新的元素）時(shí)锥余，我們需要由下至上恢復(fù)堆的順序
- 某個(gè)結(jié)點(diǎn)的優(yōu)先級下降（例如腹纳，將根結(jié)點(diǎn)替換為一個(gè)較小的元素）時(shí)，我們需要由上至下恢復(fù)堆的順序
由下至上的堆有序化 （上浮 swim）
如果堆的有序狀態(tài)因?yàn)?strong>某個(gè)結(jié)點(diǎn)變得比它的父結(jié)點(diǎn)更大了而被打破，那么我們就需要通過交換它和它的父結(jié)點(diǎn)來修復(fù)堆嘲恍。但這個(gè)結(jié)點(diǎn)仍然可能比它現(xiàn)在的父結(jié)點(diǎn)更大足画。我們可以不斷地用同樣的辦法恢復(fù)秩序。（位置 k 的結(jié)點(diǎn)的父結(jié)點(diǎn)的位置是 [k // 2]）
private void swim(int k){
while(k > 1 && less(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
def swim(pq, k):
while k > 1 and pq[int(k/2)] < pq[k]:
pq[int(k/2)], pq[k] = pq[k], pq[int(k/2)]
k = int(k / 2)
由上至下的堆有序化（下沉 sink）
如果堆的有序狀態(tài)因?yàn)?strong>某個(gè)結(jié)點(diǎn)變得比它的兩個(gè)子結(jié)點(diǎn)或其中之一更小而被打破佃牛，那么我們可以通過將它和它的兩個(gè)子結(jié)點(diǎn)中的較大者交換來恢復(fù)堆淹辞。交換可能會在子結(jié)點(diǎn)處繼續(xù)打破堆的有序狀態(tài)，因此需要不斷地用相同的方式將其修復(fù)俘侠，將結(jié)點(diǎn)向下移動(dòng)直到它的子結(jié)點(diǎn)都比它更小或是到達(dá)了堆的底部象缀。
private void sink(int k){
while (2 * k <= N){
int j = 2 * k;
if(j < N && less(j, j+1)) j++;
if(!less(k,j)) break;
exch(k, j);
k = j;
}
}
def sink(pq, k):
while(2 * k <= N):
j = 2 * k
if j < N and pq[j] < pq[j+1]: j+=1
if !pq[k] < pq[j]: break
pq[k], pq[j] = pq[j], pq[k]
k = j
sink() 和 swim() 方法是高效實(shí)現(xiàn)優(yōu)先隊(duì)列的基礎(chǔ)。
插入元素
將新元素加到數(shù)組末尾兼贡，增加堆的大小并讓這個(gè)新元素上浮到合適的位置.
刪除最大元素
從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個(gè)元素放到頂端攻冷，減小堆的大小并讓這個(gè)元素下沉到合適的位置。
class MaxPQ():
def __init__(self):
self._pq = [None]
self._index = 0
def is_empty(self):
return self._index == 0
def size(self):
return self._index
def swim(self, k):
while k > 1 and self._pq[k//2] < self._pq[k]:
self._pq[k//2], self._pq[k] = self._pq[k], self._pq[k//2]
k = k // 2
def sink(self, k):
while(2 * k <= self._index):
j = 2 * k
if j < self._index and self._pq[j] < self._pq[j+1]:
j+=1
if self._pq[k] > self._pq[j]:
break
self._pq[k], self._pq[j] = self._pq[j], self._pq[k]
k = j
def insert(self, v):
self._index += 1
if len(self._pq) <= self._index:
self._pq.append(None)
self._pq[self._index] = v
print(self._index)
self.swim(self._index)
def del_max(self):
if self.is_empty():
print("Priority Queue is empty")
return
max = self._pq[1]
self._pq[1] = self._pq[self._index]
del self._pq[-1]
self._index -= 1
self.sink(1)
return max
def show(self):
return self._pq
優(yōu)先隊(duì)列由一個(gè)基于堆的完全二叉樹表示遍希，存儲于數(shù)組 pq[1..self._index] 中等曼，pq[0] 沒有使用。在 insert() 中凿蒜，將 self._index 加一禁谦，并把新元素添加到數(shù)組最后，然后用 swim() 恢復(fù)堆的秩序废封。在 del_max() 中州泊，從 pq[1] 中得到需要返回的元素，然后將 pq[self._index] 移動(dòng)到 pq[1]漂洋，并將 self._index 減一并用 sink() 恢復(fù)堆的秩序遥皂。同時(shí)還將不再使用的 pq[-1] 刪除，以便系統(tǒng)回收它所占用的空間。
對于一個(gè)含有 N 個(gè)元素的基于堆的優(yōu)先隊(duì)列，插入元素操作只需不超過 （lgN + 1）次比較衅疙，刪除最大元素的操作需要不超過 2lgN 次比較。
對于需要大量混雜的插入和刪除最大元素操作的應(yīng)用來說样悟，命題意味著一個(gè)重要的性能突破。使用有序或是無序數(shù)組的優(yōu)先隊(duì)列的初級實(shí)現(xiàn)總是需要線性時(shí)間來完成起中一種操作庭猩，但基于堆的實(shí)現(xiàn)則能夠保證在對數(shù)時(shí)間完成它們窟她。
多叉堆
基于用數(shù)組表示的完全三叉樹構(gòu)造堆。對于數(shù)組中 1 至 N 的 N 個(gè)元素蔼水，位置 k 的結(jié)點(diǎn)大于等于位于 3k-1震糖，3k，3k+1 的結(jié)點(diǎn)趴腋，小于等于位于 (k+1) // 3 的結(jié)點(diǎn)试伙。
調(diào)整數(shù)組大小
對于靜態(tài)語言來說嘁信，可以添加一個(gè)沒有參數(shù)的構(gòu)造函數(shù)，在 insert() 中添加將數(shù)組長度加倍的代碼疏叨，在 del_max() 中添加將數(shù)組長度減半的代碼潘靖。這樣，算法的用例就無需關(guān)注各種隊(duì)列大小的限制蚤蔓。
元素的不可變性
索引優(yōu)先隊(duì)列
做到這一點(diǎn)的一種簡單方法是給每個(gè)元素一個(gè)索引卦溢。
class IndexMinPQ():
| Function(Args) | Meaning |
|---|---|
| insert(k: int, item: Item) -> None | 插入一個(gè)元素，將它和索引 k 相關(guān)聯(lián) |
| change(k: int, item: Item) -> None | 將索引為 k 的元素設(shè)為 item |
| contain(k: int) -> bool | 是否存在索引為 k 的元素 |
| delete(k: int) -> None | 刪去索引 k 及其相關(guān)聯(lián)的元素 |
| min() -> Item | 返回最小元素 |
| min_index() -> int | 返回最小元素的索引 |
| del_min() -> int | 刪除最小元素并返回它的索引 |
| is_empty() -> bool | |
| size() -> int |
索引優(yōu)先隊(duì)列用例
調(diào)用了 IndexMinPQ 的代碼 Multiway 解決了多項(xiàng)歸并問題：它將多個(gè)有序的輸入流歸并成一個(gè)有序的輸出流秀又。
如果有足夠的空間单寂，你可以把他們簡單地讀入一個(gè)數(shù)組并排序，但如果用了優(yōu)先隊(duì)列吐辙，無論輸入有多長都可以把他們?nèi)孔x入并排序宣决。
public class Multiway{
public static void merge(In[] streams){
int N = streams.length;
IndexMinPQ<String> pq = new IndexMinPQ<String>(N);
for(int i = 0; i < N; i++){
if(!streams[i].isEmpty()){
pq.insert(i, streams[i].readString());
}
}
while (!pq.isEmpty){
StdOut.println(pq.min());
int i = pq.del_min();
if(!streams.isEmpty()){
pq.insert(i, streams[i].readString());
}
}
}
public static void main(String[] args) {
int N = args.length();
In[] streams = new In[N];
for(int i = 0; i < N; i++){
streams[i] = new In(args[i]);
}
merge(streams);
}
}
class Multiway():
def __init__(self):
pass
@classmethod
def merge(cls, streams):
# streams 是 file - objects, sorted
length = len(streams)
pq = IndexMinPQ()
# file in python cannot read file word by word
# 這里按行來讀
for i in range(length):
line = streams[i].readline().strip() # strip() 把末尾的'\n'刪掉
if !line:
pq.insert(i, line)
while !pq.is_empty():
print(pq.min())
i = pq.del_min()
line = streams[i].readline().strip()
if !line:
pq.insert(i, line)
def main(*args):
streams = []
for file in args:
with open(file, mode='r') as f:
streams.append(f)
Multiway.merge(streams)
if __name__ == '__main__':
main()
這段代碼調(diào)用了 IndexMinPQ 來將作為命令行參數(shù)輸入的多行有序字符串歸并為一行有序的輸出。每個(gè)輸入流的索引都關(guān)聯(lián)著一個(gè)元素（輸入中的下一個(gè)字符串）昏苏。初始化之后尊沸，代碼進(jìn)入一個(gè)循環(huán)，刪除并打印出隊(duì)列中最小的字符串贤惯，然后將該輸入的下一個(gè)字符串添加為一個(gè)元素洼专。
from Queue import PriorityQueue
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
head = point = ListNode(0)
q = PriorityQueue()
for l in lists:
if l:
q.put((l.val, l))
while not q.empty():
val, node = q.get()
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.next
堆排序
將所有元素插入一個(gè)查找最小元素的優(yōu)先隊(duì)列，然后在重復(fù)調(diào)用刪除最小元素的操作來將他們按順序刪除孵构。
堆排序可以分為兩個(gè)階段屁商。在堆的構(gòu)造階段中，將原始數(shù)組重新組織安排進(jìn)一個(gè)堆中颈墅；然后在下沉排序階段蜡镶，我們從堆中按遞減順序去除所有元素并得到排序結(jié)果。
堆的構(gòu)造
更聰明高效的做法是從右至左用 sink() 函數(shù)構(gòu)造子堆恤筛。數(shù)組的每個(gè)子位置都已知都一個(gè)子堆的根結(jié)點(diǎn)帽哑，sink() 對于這些子堆也適用。如果一個(gè)結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都已經(jīng)是堆了叹俏，那么在該結(jié)點(diǎn)上調(diào)用 sink() 可以將它們變成一個(gè)堆。這個(gè)過程會遞歸地建立起堆的秩序僻族。開始時(shí)我們只需要掃描數(shù)組中的一半元素粘驰，因?yàn)槲覀兛梢蕴^大小為 1 的子堆。
public static void sort(Comparable[] pq){
int N = pq.length
for(int k = N / 2; k >= 1; k--){
sink(1, k, N);
}
while(N > 1){
exch(pq, 1, N--)
sink(pq, 1, N)
}
}
def sort(pq):
N = len(pq)
for k in range(N / 2, 0, -1):
sink(pq, k, N)
while N > 1:
pq[1], pq[N] = pq[N], pq[1]
N -= 1
sink(pq, 1, N)
這段代碼用 sink() 方法將 pq[1] 到 pq[N] 的元素排序述么。for 循環(huán)構(gòu)造了堆蝌数，然后 while 循環(huán)將最大的元素 pq[1] 和 pq[N] 交換并修復(fù)了堆，如此重復(fù)直到堆變空度秘。
下沉排序
堆排序的主要工作都是在第二階段完成的顶伞。這里將堆中的最大元素刪除饵撑，然后放入堆縮小后數(shù)組中空出的位置。這個(gè)過程和選擇排序有些類似唆貌，但所需的比較要少得多滑潘，因?yàn)槎烟峁┝艘环N從未排序部分找到最大元素的有效方法。
將 N 個(gè)元素排序锨咙，堆排序只需少于（2NlgN + 2N ）此比較（以及一半次數(shù)的交換）语卤。
先下沉后上浮
改進(jìn)基于堆的優(yōu)先隊(duì)列的實(shí)現(xiàn)和堆排序的方法。
堆排序在排序復(fù)雜性的研究中有著重要的地位酪刀，因?yàn)樗俏覀兯奈┮荒軌蛲瑫r(shí)最有地利用空間和時(shí)間的方法 -- 在最壞的情況下他也能保證使用 ～ 2NlgN 次比較和恒定的額外空間粹舵。當(dāng)代碼空間十分緊張的時(shí)候它很流行，因?yàn)樗挥脦仔芯湍軐?shí)現(xiàn)較好的性能骂倘。但現(xiàn)代系統(tǒng)的許多應(yīng)用很少使用它眼滤，因?yàn)樗鼰o法利用緩存。數(shù)組元素很少和相鄰的其他元素進(jìn)行比較历涝，因此緩存未命中率要遠(yuǎn)遠(yuǎn)高于大多數(shù)比較都在相鄰元素間進(jìn)行的算法诅需，如快速排序，歸并排序睬关，甚至是希爾排序诱担。
另一方面，用堆實(shí)現(xiàn)的優(yōu)先隊(duì)列在現(xiàn)代應(yīng)用程序中越來越重要电爹，因?yàn)樗茉诓迦氩僮骱蛣h除最大元素操作混合的動(dòng)態(tài)場景中保證對數(shù)級別的運(yùn)行時(shí)間蔫仙。
