在多用戶環(huán)境中，操作系統(tǒng)調(diào)度程序必須決定在若干進程中運行哪個進程。一般只允許一個進程運行一個固定的時間片吏夯。一種算法是使用一個隊列玄糟。開始時將作業(yè)放到隊列的末尾勿她。調(diào)度程序?qū)⒎磸吞崛￡犃兄械牡谝粋€作業(yè)并運行它直到運行完畢，或者在該作業(yè)的時間片用完但未運行完畢時把它放到隊列的末尾阵翎。這種策略一般并不太合適逢并，因為一些很短的作業(yè)由于一味等待運行而要花費很長的時間去處理。一般說來郭卫，短的作業(yè)要盡快地結(jié)束砍聊，這一點很重要，因此在已運行過的作業(yè)當中這些短作業(yè)應該擁有優(yōu)先權贰军。此外玻蝌，有些作業(yè)雖不短小但很重要，也應用擁有優(yōu)先權词疼。這種特殊的應用需要一類特殊的隊列俯树，我們稱之為優(yōu)先隊列（priority queue）。
模型
優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構：Insert（插入）贰盗，它的工作是顯而易見的许饿；以及 DeleteMin（刪除最小者），它的工作是找出舵盈、返回和刪除優(yōu)先隊列中最小的元素陋率。Insert 操作等價于 Enqueue（入隊），而 DeleteMin 則是隊列中 Dequeue（出隊）在優(yōu)先隊列中的等價操作秽晚。DeleteMin 函數(shù)也變更它的輸入瓦糟。軟件工程界當前的想法認為這不再是一個好的思路。不過赴蝇，處于歷史原因我們還是需要使用這個函數(shù)狸页；許多程序設計人員期望 DeleteMin 以這種方式運行。
如果大多數(shù)數(shù)據(jù)結(jié)構那樣，有時可能要添加一些操作芍耘，但這些添加的操作屬于拓展的操作址遇，不屬于基本模型。
除了操作系統(tǒng)外斋竞，優(yōu)先隊列還有許多應用倔约。比如，可以用于外部排序坝初，在貪婪算法（greedy algorithm）的實現(xiàn)方面優(yōu)先隊列也很重要浸剩，該算法通過反復求出最小元來進行計算。
一些簡單的實現(xiàn)
有幾種明顯的方法實現(xiàn)優(yōu)先隊列鳄袍。
- 我們可以使用一個簡單的鏈表在表頭以
執(zhí)行插入操作绢要，并遍歷該鏈表以刪除最小元，這又需要
時間拗小。
- 另一種方法是重罪，始終讓表保持排序狀態(tài)；這使得插入代價高昂（
- 還有一種實現(xiàn)優(yōu)先隊列的方法是使用二叉查找樹呼胚，它對這兩種操作的平均運行時間都是
。盡管插入是隨機的息裸，而刪除則不是蝇更，但是這個結(jié)論還是成立的。記住我們刪除的唯一元素是最小元呼盆。反復除去左子樹中的節(jié)點似乎損害樹的平衡年扩，使得右子樹加重。然而宿亡，右子樹是隨機的。在最壞的情形（即 DeleteMin 將左子樹刪空的情況）下纳令，右子樹擁有的元素最多也就是它應具有的兩倍挽荠。這只是在其期望的深度上加了一個小常數(shù)。注意平绩，通過使用平衡樹圈匆，可以把界變成最壞情形的界，這將防止出現(xiàn)壞的插入序列捏雌。
使用查找樹可能有些過分跃赚，因為它支持許許多多并不需要的操作。大多數(shù)情況下，我們使用的基本的數(shù)據(jù)結(jié)構不需要指針纬傲，它以最壞情形時間 支持上述兩種操作满败。插入實際上將花費常數(shù)平均時間，若無刪除干擾叹括，該結(jié)構的實現(xiàn)將以線性時間建立一個具有 N 項的優(yōu)先隊列算墨。然后，如果實現(xiàn)優(yōu)先隊列以支持有效的合并汁雷，這個附加的操作似乎有些復雜净嘀，它顯然需要使用指針。
二叉堆
有一種工具叫作二叉堆（binary heap）侠讯，常用其實現(xiàn)優(yōu)先隊列挖藏，當不加修飾地使用堆（heap）這個詞時一般都是指該數(shù)據(jù)結(jié)構的實現(xiàn)。這里厢漩，我們直接把 二叉堆 叫作 堆膜眠。同二叉查找樹一樣，堆也有兩個性質(zhì)袁翁，即結(jié)構性和堆序性柴底。正如 AVL 樹一樣，對堆的一次操作可能破壞這兩個性質(zhì)中的一個粱胜，因此柄驻，堆的操作必須要到堆的所有性質(zhì)都被滿足時才終止。事實上這并不難做到焙压。
結(jié)構性質(zhì)
堆是一棵被完全填滿的二叉樹鸿脓，有可能的例外是在底層，底層上的元素從左到右填入涯曲。這樣的樹被稱為完全二叉樹（complete binary tree）野哭。
很容易證明，一棵高為 的完全二叉樹有
到
個節(jié)點幻件。這意味著拨黔，完全二叉樹的高是
，顯然它是
的绰沥。
一項重要的觀察發(fā)現(xiàn)篱蝇，因為完全二叉樹很有規(guī)律，所以它可以用一個數(shù)組表示而不需要指針徽曲。
對于數(shù)組中任意位置 上的元素零截，其左兒子在位置
上，右兒子在左兒子后的單元
中秃臣，它的父親則在位置
上涧衙，因此，不僅這里不需要指針，而且遍歷該樹所需要的操作也極其簡單弧哎，在大部分計算機上運行得速度可能會非逞惚龋快。這種實現(xiàn)方法的唯一問題在于傻铣，最大的堆大小需要事先估計章贞，但對于典型的情況這并不成問題。
因此非洲，一個堆數(shù)據(jù)結(jié)構將由一個數(shù)組（不管關鍵字是什么類型）鸭限、一個代表最大值的整數(shù)以及當前的堆大小組成。
堆序性質(zhì)
使操作快速執(zhí)行的性質(zhì)是堆序（heap order）性两踏。由于我們想要快速地找出最小元败京，因此最小元應該在根上。如果我們將任意子樹也視為一個堆梦染，那么任意節(jié)點就應該小于它的所有后裔赡麦。
應用這個邏輯，我們得到堆序性質(zhì)帕识。在一個堆中泛粹，對于每一個節(jié)點 X，X 的父親中的關鍵字小于（或等于）X 中的關鍵字肮疗，根節(jié)點除外（它沒有父親）晶姊。
根據(jù)堆序性質(zhì)，最小元總可以在根處找到伪货。因此们衙，我們以常數(shù)時間完成附加運算 FindMin。
基本的堆操作
無論從概念上還是實際上考慮碱呼，執(zhí)行這兩種所要求的操作都是容易的蒙挑，只需要始終保持堆序性質(zhì)。
Insert(插入)
為將一個元素 X 插入到堆中愚臀，我們在下一個空閑位置創(chuàng)建一個空穴忆蚀，否則該堆將不是完全樹。如果 X 可以放在該空穴中而并不破壞堆的序姑裂，那么插入完成馋袜。否則，我們把空穴的父節(jié)點上的元素移入該空穴中炭分，這樣桃焕，空穴就朝著根的方向上行一步剑肯。繼續(xù)該過程直到 X 能被放入空穴中為止捧毛。如圖 6-6 所示，為了插入 14，我們在堆的下一個可用位置建立一個空穴呀忧。由于將 14 插入空穴破壞了堆序性質(zhì)师痕，因此將 31 移入該空穴。在圖 6-7 中繼續(xù)這種策略而账，直到找出置入 14 的正確位置胰坟。
這種一般的策略叫作上濾（percolate up）：新元素在堆中上濾直到找出正確的位置。
代碼實現(xiàn)如下：
/* H->Element[0] is a sentinel */
void
Insert(ElementType X, PriorityQueue H)
{
int i;
if( IsFull(H))
{
Error(" Priority queue is full");
return;
}
for( i = ++ H->Size; h->Elements[i/2]>X; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = X;
}
其實我們本可以使用 Insert 例程通過反復實施交換操作直至建立正確的序來實現(xiàn)上濾過程泞辐，可是一次交換需要三條賦值語句笔横。如果一個元素上濾 曾，那么由于交換而實施的賦值的次數(shù)就達到
咐吼，而這里的方法卻只用
次賦值吹缔。
如果要插入的元素是新的最小值，那么它將一直被推向頂端锯茄。這樣在某一時刻厢塘， 將是 1，我們就要令程序跳出 while 循環(huán)肌幽。當然我們可以用明確的測試做到這一點晚碾，不過，我們采用的是把一個很小的值放到位置 0 處以使 while 循環(huán)得以終止喂急。這個值必須保證小于（或等于）堆中的任何值格嘁，我們稱之為標記（sentinel）。這種想法類似于鏈表中頭節(jié)點的使用煮岁。通過添加一條啞信息（dummy piece of information）讥蔽，我們避免了每個循環(huán)都要執(zhí)行一次測試，從而節(jié)省了一些時間画机。
如果欲插入的元素是新的最小元從而一直上濾到根處冶伞，那么這種插入的時間高達。平均看來步氏，這種上濾終止得要早响禽；已證明，執(zhí)行一次插入平均需要 2.607 次比較荚醒，因此 Insert 將元素平均上移 1.607 層芋类。
DeleteMin（刪除最小元）
DeleteMin 以類似于插入的方式處理。找出最小元是容易的界阁，困難的部分是刪除它侯繁。當刪除一個最小元時，在根節(jié)點處產(chǎn)生了一個空穴泡躯。由于現(xiàn)在堆少了一個元素贮竟，因此堆中最后一個元素 X 必須移動到該堆的某個地方丽焊。如果 X 可以放到空穴中，那么 DeleteMin 完成咕别。不過這一般不太可能技健，因此我們將空穴的兩個兒子中較小者移入空穴，這樣就把空穴向下推了一層惰拱。重復該步驟直到 X 可以放入空穴雌贱。因此，我們的作法是將 X 置入沿著從根開始包含最小兒子的一條路徑上的一個正確的位置偿短。
在圖 6-9 中左邊的圖顯示 DeleteMin 之前的堆欣孤。刪除 13 后，我們必須要正確地將 31 放到堆中昔逗。31 不能放在空穴中导街，因為這將破壞堆序性質(zhì)。于是纤子，我們把較小的兒子 14 置入空穴搬瑰，同時空穴下滑一層（見圖 6-10）。重復該過程控硼，把 19 置入空穴泽论，在更下一層上建立一個新的空穴。然后卡乾，再把 26 置入空穴翼悴，在底層又建立新的空穴。最后幔妨，我們得以將 31 置入空穴（見圖 6-11）鹦赎。這種一般的策略叫作下濾（percolate down）。在其實現(xiàn)例程中我們使用類似于 Insert 例程中用過的技巧來避免進行交換操作误堡。
在堆的實現(xiàn)中經(jīng)常發(fā)生的錯誤是當堆中存在偶數(shù)個元素的時候古话，此時將遇到一個節(jié)點只有一個兒子的情況。不要假設節(jié)點總有兩個兒子锁施，因此這就涉及一個附加的測試陪踩。一個極其巧妙的解決辦法是始終保證你的算法把每一個節(jié)點都看成有兩個兒子。為了實施這種解法悉抵，當堆的大小為偶數(shù)時肩狂，在每個下濾開始時，可將其值大于堆中的任何元素的標記放到堆的終端后面的位置上姥饰。你必須在深思熟慮以后再這么做傻谁，而且必須要判斷你是否確實要使用這種技巧。雖然這不再需要測試右兒子的存在性列粪，但是你還是需要測試何時到達底層审磁，因為對每一片樹葉算法將需要一個標記荆秦。
這種算法的最壞情形運行時間為 。平均而言力图，放在根處的元素幾乎下濾到堆的底層（它所來自的那層），因此平均運行時間為
掺逼。
其他的堆操作
注意吃媒，雖然求最小值操作可以在常數(shù)時間完成，但是吕喘，按照求最小元設計的堆（也稱作最小值（min）堆）在求最大元方面卻無任何幫助赘那。事實上，一個堆所蘊含的關于序的信息很少氯质，因此募舟，若不對整個堆進行線性搜索，是沒有辦法找出任何特定的關鍵字的闻察。在很多大型堆結(jié)構中拱礁，半數(shù)的元素位于樹葉上，此時辕漂，如果重要的是要知道元素都在什么地方呢灶，那么除堆之外，還必須用到諸如散列表等某些其他的數(shù)據(jù)結(jié)構钉嘹。
如果我們假設通過某種其他方法得知每一個元素的位置鸯乃，那么有幾種其他操作的開銷將變小。下述三種這樣的操作均以對數(shù)最壞情形時間運行跋涣。
DecreaseKey（降低關鍵字的值）
操作降低在位置 P 處的關鍵字的值缨睡，降值的幅度為正的量
。由于這可能破壞堆的序陈辱，因此必須通過上濾對堆進行調(diào)整奖年。該操作對系統(tǒng)管理程序是有用的：系統(tǒng)管理程序能夠使它們的程序以最高的優(yōu)先級運行。
IncreaseKey（增加關鍵字的值）
操作增加在位置 P 處關鍵字的值沛贪，增值的幅度為正的量
拾并。這可以用下濾來完成。許多調(diào)度程序自動地降低正在過多地消耗 CPU 時間的進程的優(yōu)先級鹏浅。
Delete（刪除）
操作刪除堆中位置 P 上的節(jié)點嗅义。這通過首先執(zhí)行
，再執(zhí)行
來完成隐砸。當一個進程被用戶終止（而不是正常終止）時之碗，它必須從優(yōu)先隊列中除去。
BuildHeap（構建堆）
操作把 N 個關鍵字作為輸入并把它們放入空堆中季希。顯然褪那，這可以使用 N 個相繼的 Insert（插入）來完成幽纷。由于每個 Insert 將花費
平均時間以及
的最壞情形時間，因此該算法的總運行時間則是
平均時間而不是
最壞情形時間博敬。由于這是一種特殊的指令友浸，沒有其他操作干擾，而且我們已經(jīng)知道該指令能夠以線性平均時間實施偏窝，因此收恢，期望能夠保證線性時間界的考慮是合乎情理的。
定理：包含 個節(jié)點祭往、高為
的理想二叉樹（perfect binary tree）的節(jié)點的高度和為
伦意。
