批量構造問題
前一節介紹最小堆及單次優先隊列操作。本節輸入為一個含 個鍵值的任意陣列,鍵值來自全序集合;目標是把它重排成最小堆,而不遺失或複製鍵值。使用從一開始索引的陣列 。當索引不超過 ,索引 的子節點為 和 。最小堆要求每個父節點的鍵值不大於每個現有子節點。空陣列及單元素陣列已符合此性質。
逐個插入所有鍵值可用 次比較。自底向上的構造則依次在索引 執行下濾。所有更大的索引都是葉節點。我們使用確定的約定:選取較小的子節點;若兩個子鍵值相等則選左子節點;若父鍵值已不大於所選子鍵值便停止。
下濾及其前提
定義 3.2.1
(索引處的近似堆)
若 的現有子節點為根的子樹都是最小堆,而 本身的鍵值卻可能大於某個子鍵值,就稱陣列在 處是近似堆。節點 的高度 ,是在完整陣列樹中由 向下的最長路徑所含的邊數。
在 下濾時,假設陣列在 處是近似堆。若 沒有子節點便停止。否則選較小的現有子節點 。若 ,便停止;因 是最小的子節點,根不大於兩個子節點,而整棵子樹已是堆。若 ,交換兩個鍵值,並在 繼續。
引理 3.2.2
(下濾修復近似堆)
若陣列在 處是近似堆,則在 下濾至多交換 次後終止,使以 為根的子樹成為鍵值不變的最小堆,且不改變其他位置。
證明
(把可能的違反向下移一層)
設目前索引 處近似堆條件成立, 為較小的子節點。若沒有交換,根不大於兩個子節點,而兩棵子樹都是堆,所以整棵子樹是堆。若 並交換,舊鍵值 移到 , 移到 。交換前,由子樹是堆的假設, 不大於其自己的子節點;由選取方式,它也不大於兄弟節點。交換後,它成為 的新根,且不大於兩個子節點:移下的舊父鍵值嚴格較大,兄弟節點原本亦不小於 。未觸及的子樹仍是堆。只有 為根的子樹可能違反堆次序,而它的兩棵子樹仍是堆,所以近似堆條件在 處成立。索引嚴格向下移動,因此過程至多交換 次,並在葉節點或已符合條件的根停下。交換保持鍵值多重集不變,並只觸及該子樹內的位置。
證明透視
子樹是堆的假設用在哪裏
兩棵子樹都是堆這個假設,每次交換用一次:用來確定上移的鍵值 不大於 之下的一切。選較小子節點則用一次:用來確定它也不大於兄弟。若其中一項不成立, 處的新根仍可能大於其下的某個鍵值,單次向下走便不足夠。這條路徑會終止,因為索引嚴格增加;它在葉節點,或在鍵值已不大於其較小子節點的節點處完結。
定理 3.2.3
(自底向上構造是正確的)
按遞減次序處理索引 ,並各自下濾,可把任何陣列變成恰好含原有鍵值的最小堆。
證明
(對遞減索引作歸納)
在處理 之前,每個子節點的索引較大,其子樹已是堆:它不是葉節點,就是其下濾已較早完成,而且之後沒有任何下濾改變過它的子樹,因為每次下濾只改變自己索引的子樹,而嚴格介乎 與該子節點之間的索引都不是該子節點的祖先。所以陣列在 處是近似堆, 的下濾使以 為根的子樹成為堆。歸納至 ,便證明最終陣列是最小堆,且恰好保留原有鍵值。不保證相等鍵值之間的穩定次序。
反例模式
按遞增次序處理索引
斷言:依哪個次序處理索引 都沒有關係。取 ,依 的次序下濾。在索引 , 先與較小子節點 交換,再與其新位置 的較小子節點 交換,得到 。在索引 ,鍵值 不大於其子節點 和 ,沒有變化。在索引 , 與 交換,得到 。根 大於其子節點 ,所以結果不是堆。在索引 時,子節點為根的子樹還不是堆,前提不成立;遞減次序正好保證前提成立。
為何構造是線性時間
定理 3.2.4
(建堆的線性界)
當 ,所有節點高度之和滿足 。因此自底向上構造總共少於 次交換,並使用 次鍵值比較。
證明
(按高度為節點計數)
由 開始下濾至多向下交換 次。節點高度至少為 ,當且僅當其最左可能後代索引 存在,因此此類節點至多有 個。對可能的向下層數作雙重計數,得到
最後的和是有限和,因為各項最終為零。每層至多使用常數次鍵值比較,而迴圈至多啟動 次下濾;故在比較及存取均為常數時間的模型下,整體構造使用 次比較和交換。當 ,迴圈不執行。
陣列原地重用,因此迭代式下濾只需 額外空間。此界是建立堆的成本,不是完整排序陣列的成本。
追蹤例子
例題 3.2.5
(七個鍵值的陣列)
從 開始。最後一個非葉節點的索引是 。
| 處理索引 | 下濾後的陣列 |
|---|---|
| 3 | |
| 2 | |
| 1 |
在索引 ,鍵值 先與 交換,再與 交換。最終根是最小值,但兄弟節點及子樹一般沒有整體排序。
例題 3.2.6
(n = 7 時的交換次數)
節點 的高度為 ,總和 。這與計數論證吻合:高度至少為 要求 ,共三個節點;高度至少為 要求 ,一個節點;高度至少為 要求 ,沒有節點。在上面的追蹤中,各次下濾交換了 次,所以每次下濾都用盡其高度,交換次數等於 。
例題 3.2.7
(相等鍵值與很小的輸入)
對 ,只有索引 是非葉節點。兩個子節點鍵值同為 ,左子節點規則選索引 ;因 而交換,得 。若改選右子節點,則得 ;兩者都是堆。對 ,索引 只有索引 一個子節點, 得 。當 或 ,沒有非葉索引,陣列不變。
常見錯誤
(把堆當成已排序的陣列)
第一個追蹤的結果 是有效的堆,但沒有排序:位置 的 大於位置 的 。堆只保證每個鍵值不大於其子節點,所以只知道根是最小值。要得到已排序的輸出,還需要更多工作。
習題
快速檢查
(對 套用上述約定,給出處理索引 、、 後各自的陣列。)
索引 只有索引 一個子節點。
解答 · 答案
陣列依次為 、、。
快速檢查
(以子鍵值相等時選左方的規則,從 建堆。為何改變平局規則後,即使結果陣列可能不同,正確性仍保持?)
比較兩個相等的子節點作為候選。
解答 · 答案
結果為 。兩個相等子節點任選其一都是最小子節點,因此局部堆論證仍適用;相等鍵值的次序不一定穩定。
快速檢查
(解釋為何把每次下濾分別界定為 ,只能證明 ;指出得到較精確上界所需的額外事實。)
有多少個節點是很高的?
解答 · 答案
該估計向每個節點都收取最大可能高度的成本。高度至少為 的節點至多有 個,故把實際高度界相加,總向下層數少於 。