動機
已排序的陣列記錄了每一對鍵之間的次序。堆記錄的資訊較少:每個父節點都支配其子節點,因此無須對其餘鍵排序,也能輕易找到最大鍵。這種偏序支持反覆取出最大元素,也支持一種直接使用輸入陣列本身作為儲存的排序算法。
出人意料的是建堆的成本。對單個頂點作下沉可能需要對數時間,但對每個頂點都建堆,總時間是線性的,而不是頂點數乘以對數。大多數頂點靠近葉子,可下移的距離很短。證明的方法是統計每種高度至多有多少個頂點,而不是讓所有頂點都按根的最壞高度計算成本。
所有界都按常數成本的鍵比較和普通陣列存取計算;若鍵的表示較昂貴,則必須把比較的成本計入。
定義
定義 8.2.1
(陣列形狀與最大堆序)
大小為 的堆佔用陣列的第一至第 個位置,具有完全二叉樹的形狀:位置 的子節點為 與 (在大小範圍之內時),非根節點的父節點為 。陣列按層由左至右填充。
最大堆要求在每一對父子之間都有 ,且只比較鍵。頂點的高度是它到後代葉子的最大邊數。葉子的高度為零。當 時,根的高度至多為 。
活動堆可以只是較長陣列的一個前綴;即使陣列中存在超出目前大小的位置,那些位置上的子節點也要忽略。記錄除鍵之外還可以帶有身份標籤。穩定排序保持鍵相等的記錄的原有相對次序,這一條件與數值上是否有序是分開的。
定義 8.2.2
(迭代式下沉)
假設所選位置的兩棵子樹都已經是堆。比較其現有子樹的兩個根,選取其中較大的一個。若該子節點的鍵大於目前的鍵,則交換兩者,並在該子節點的位置繼續。否則停止。到達葉子時也停止。當兩個子節點的鍵相等時,任何固定的選擇規則都有效。每一步都以目前活動堆的邊界為準。
下沉的實作只需用常數輔助空間儲存目前索引、所選子節點索引和一條暫存記錄。遞歸版本還會額外使用調用堆疊;下文常數空間的排序結論使用的是這一迭代常式。
定理/命題
定理 8.2.3
(下沉修復單個根處的違例)
在上述子樹假設下,下沉在所選的整棵子樹上產生一個堆,並保持其記錄的多重集不變。對於起始高度 ,它的工作量為 ,每檢驗一層至多作兩次鍵比較,向下交換不超過 次。
定理 8.2.4
(由下而上建堆是線性的)
對含 條記錄的陣列,依次在位置 上作下沉。結果是一個最大堆。建堆的總時間為 ,因為對非空輸入有
空陣列無須下沉,本身已是堆。
定理 8.2.5
(堆排序以固定後綴在原陣列內排序)
先在整個輸入上建立最大堆。對活動大小 ,把根與位置 交換,將活動邊界降為 ,並對新的根作下沉。最終陣列按鍵非遞減有序,且記錄與輸入相同。
對於鍵互不相同的輸入,隨著 增長,其最壞時間為 ;其迭代實作除輸入陣列外只使用 輔助空間。它一般是不穩定的。空陣列與單條記錄的情形不執行取出迴圈。
這一看似特別的儲存優勢只需要一個陣列和一個變動的活動前綴邊界。這並不是說無論編碼如何,鍵值都能放進一個機器字。鍵相等的不同記錄即使在比較次序已經正確時也可能被移動。
證明思路或證明
證明
(下沉的正確性與成本)
對於下沉:堆的根沿父子鏈的遞移性支配其整棵子樹。因此較大的子樹根支配該子樹中的每個鍵,若還有另一個子節點,也支配另一個子樹根。若目前的鍵同時支配兩個子樹根,則所有父子約束都成立,過程正確停止。
否則與較大的子節點交換。新的頂部鍵支配原來的目前鍵以及原來的兩棵子樹。下移記錄之上的所有約束現已正確;只有該記錄的新位置可能違反其下方的次序。它自己的子樹未受影響,仍是堆,因此同樣的論證可以重複。每次交換,目前索引嚴格下降,所以交換次數至多等於起始高度。在停止位置或葉子處,剩餘的違例消失。交換完全保持記錄不變。
每檢驗一層至多需要一次子節點之間的比較和一次與目前鍵的比較。在葉子之上仍會發生一次最後的不交換檢驗,它包含在原有的高度界之內。這證明了成本估計,其中包括高度為零時迴圈設定的常數開銷。
證明
(為甚麼按索引遞減建堆是線性的)
對於建堆:任何工作開始之前,每個葉子都是堆。按索引遞減處理到索引 時,其子節點的位置更大,因此它們要麼已被處理,要麼是葉子。於是下沉的假設成立,由歸納法可知每個被處理的子樹都是堆。最後對根的一步涵蓋整棵樹。
為統計工作量:索引為 、高度至少為 的頂點,其後代的索引至少為 ,因此必須滿足 。所以高度至少為 的頂點至多有 個。對高度的指示量求和即得所示等式,而幾何級數的上界小於 。每個被處理頂點的額外常數工作量同樣是線性的。該證明使用了完全的陣列樹形狀;它不能把同樣的頂點數估計用於任意不平衡的二叉樹。
證明透視
建堆對不同的高度求和,而不是用同一個最壞情形
關鍵一步是把求和次序顛倒:不是問每個頂點最多能下沉多遠,而是問有多少個頂點能下沉至少 層。完全的陣列形狀只在一處使用,就是得出這種頂點必須滿足 ;按索引遞減的次序只用來提供下沉所需的假設,即兩棵子樹都已是堆。除此以外,鍵的取值並無影響。
計數這一步不能去掉形狀假設。若二叉樹是由 個頂點串成的一條路徑,各頂點高度為 ,總和是 ,是平方階。把每個頂點都乘以根的對數界,是有效但寬鬆的上界,錯過了只有平衡形狀才能提供的線性保證。
證明
(堆排序的不變式與運行時間)
對於堆排序,維持如下不變式:活動前綴是堆,後綴已排序,且每個活動鍵至多等於每個後綴鍵。起初後綴為空,建堆給出堆。根是活動記錄中的一個最大值。把它與活動的最後一個位置交換,就把該最大值接到後綴之前,它不大於任何已固定的後綴鍵。移除該位置後,前綴仍保持完全樹的形狀,只有它的新根可能違反堆序。下沉修復之。歸納法證明了所有步驟,最後剩下一條記錄的前綴使有序性完整。記錄得以保存,是因為整個過程只有交換。
建堆花費線性時間,至多 次取出步驟各花費 ,由此得到上界。對於鍵互不相同的比較排序,二元決策樹必須區分全部 種可能的相對次序。其最壞深度至少為 ,由於最大的一半因子都至少為 ,這是 。已證明的正確性使堆排序受此下界約束,從而得到所述的最壞階。這並不意味著每個含相等鍵的輸入都要花這麼長時間。
優先隊列操作與記憶體配置假設
堆根可在常數時間內給出最大值。在陣列容量足夠時插入:把新記錄附加到末端,只要它大於其父節點就向上交換。只有這條祖先鏈可能出現新的違例;交換修復了它的下端邊,並使可能的違例向根的方向移動。該鏈的長度是對數的。取出最大值時,用最後一條記錄取代根,縮短堆;若仍有記錄,則對根作下沉。子樹仍是堆。當儲存空間已經可用時,這些操作的最壞情形比較與存取成本都是對數的。
擴充底層陣列可能另外複製所有記錄。前面的界並不會使這次複製消失。倍增陣列有前面已證明的另一個攤還保證,而某次觸發擴容的插入在實際物理工作量上仍可能是線性的。大小固定的堆排序陣列無須這種擴容,所以它的輔助空間分析與每次取出的分析都不受影響。
例題詳解
例題 8.2.6
(六個鍵上的由下而上建堆)
從 開始。位置三已經支配它唯一的子節點。對位置二作下沉,把一與五交換,得到 。在根處,先把三與六交換,再在其新位置與四交換。結果是 。
兄弟鍵五和四之間無須按任何指定方向排序;它們各自只受自己的父節點和子節點約束。所得陣列是堆,是因為五條父子不等式全部成立,而不是因為順序讀出這個陣列會得到有序序列。
例題 8.2.7
(有序後綴在增長,而活動前綴在變化)
從該堆出發,把六與最後的三交換。活動前綴變為 ,固定後綴為六。下沉後得到活動前綴 。接著把五與活動的最後一個鍵二交換,並再次縮短;下沉後得到 ,其後是後綴 。
在檢驗子節點時必須排除後綴。它的大鍵已經處於最終位置;若容許它們回到活動堆中,就會破壞進展不變式。此時活動根四是剩餘鍵中最大的,而不是整個陣列中最大的。
例題 8.2.8
(插入與取出沿著一條根路徑移動)
在容量足夠的情況下,把七插入堆 。它被附加在位置七,與位置三的父節點四交換,再與根六交換。堆變為 。
取出七時,把最後的四移到根,並把堆縮短為六個元素。把該四與子節點六交換,又得到 。其他分支的堆不等式始終保持。只需找出並修復一條祖先路徑或後代路徑即可,因為操作之前的狀態已經是堆。
概念視角結構
堆只儲存回答它下一個問題所需的比較
父子序使最大值可以直接取得,同時讓大多數兄弟與堂兄弟之間的比較保持未決。反覆取出逐步確定出整個輸出次序。完全形狀控制操作的深度,偏序的鍵序決定哪條記錄可以被取出;只靠其中任何一個性質都不足以構成這個算法。
常見錯誤
反例模式
鍵相等的記錄可能被最後的交換顛倒
取兩條記錄 ,輸入次序如此。因為鍵相等,建堆時它們保持原位。排序的取出步驟仍然交換根與最後一個位置,得到 。鍵被正確排序,但鍵相等的記錄的身份次序被顛倒,所以這種堆排序不是穩定的。穩定性是關於鍵相等時記錄次序的性質,而不僅僅是排序後鍵值的性質。
常見錯誤
(對子樹尚未成堆的根作下沉)
下沉只把一條記錄與它的兩個子節點比較,所以它只修復頂部的違例,其他位置一概不管。取 ,位置二的一位於其子節點五和四之上。對位置一作下沉,是把三與較大的子節點二比較,沒有發現違例就停止,結果仍是 。它不是堆,因為一在五之上。這就是建堆必須按索引遞減進行的原因:這樣每次下沉開始時,其兩棵子樹都已是堆。
常見錯誤
(讓下沉看到已排序的後綴)
堆排序過程中活動邊界不斷縮小,邊界之外的子節點必須忽略。把 的根與最後的活動鍵交換後,狀態是 。把一下沉,得到 。若常式仍使用整個陣列的長度,就會把一與它看似的子節點四和五比較,並與五交換,得到 ,其中後綴變成 ,不再有序。
堆陣列不必整體有序。透過反覆插入來建堆,其成本分析與由下而上建堆不同。遞歸的下沉常式並不會因為重用了陣列本身就擁有常數的調用堆疊空間。在排序和優先隊列更新的過程中,堆的大小與陣列配置的長度必須保持區分。
總結
在兩棵子樹都是堆之後,下沉可以修復一個根。按索引遞減建堆滿足這一假設,而且是線性的,因為完全樹中的頂點高度總和是線性的。堆排序反覆把一個最大值放入固定的有序後綴,取出的工作量是對數的,迭代實作的輔助儲存是常數,而鍵相等時的穩定性以及底層陣列的配置仍各自有其獨立條件。
練習
快速檢查
(一棵完美二叉樹的高度為 ,頂點數為 。計算所有頂點高度之和。)
利用每個正整數層級上高度至少為該層級的頂點個數。
解答 · 答案
對 ,恰有 個頂點的高度至少為 。求和得 。當 時結果為零,與單個葉子相符。即使根的高度增長,這一結果也使建堆的線性求和變得明確。
快速檢查
(給出一個既不是遞增也不是遞減排列的最大堆陣列。並解釋為甚麼每個非遞增陣列都是最大堆。)
比較索引次序與父子索引關係。
解答 · 答案
陣列 是有效的最大堆,因為根五支配兩個子節點。它不是非遞減的,因為五大於三;也不是非遞增的,因為三小於四。反之,在非遞增陣列中,每個父節點的索引都小於其各個子節點的索引,所以它的鍵至少等於子節點的鍵。因此全部堆不等式都成立。因此每個非遞增陣列都是堆,而其逆不成立。
快速檢查
(從例題中的堆排序狀態(活動前綴 、已排序後綴 )繼續,直至完成。寫出每次取出時的活動邊界。)
不要下沉到固定的後綴中。
解答 · 答案
活動大小為四時,把根四與一交換,得到活動前綴 與後綴 。下沉後為 。活動大小為三時,把三與二交換,得到前綴 與後綴 ;它已經是堆。活動大小為二時,把二與一交換,剩下單個活動鍵一,後綴為 。完整的陣列是 ,並且沒有任何後綴項在被固定之後參與下沉。