參考資料：《算法導(dǎo)論》第三版
深度優(yōu)先搜索
一個(gè)圖中所有不在深度優(yōu)先搜索樹中的邊，都是后向邊
在對(duì)無向圖的深度優(yōu)先搜索中，從來不會(huì)出現(xiàn)前向邊和橫向邊
MAX-HEAPIFY時(shí)間復(fù)雜度：O(lgn)
BUILD-MAX-HEAP時(shí)間復(fù)雜度：線性時(shí)間復(fù)雜度。功能：從無需的輸入數(shù)組中構(gòu)造一個(gè)最大堆。（堆）
HEAPSORT：時(shí)間復(fù)雜度為O(nlgn)。功能是對(duì)一個(gè)數(shù)組進(jìn)行原址排序。（數(shù)組本身）
一個(gè)栗子。
Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102.
第一步：先把這些數(shù)據(jù)放進(jìn)一個(gè)列表里。[142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102]。然后構(gòu)建一個(gè)堆的圖形。
第二步：調(diào)用BUILD-MAX-HEAPIFY。從最后一個(gè)parent開始，一直到parent。
第三步：調(diào)用HEAPSORT。具體就是把堆的root元素和最后一個(gè)元素交換，并把這個(gè)root元素放進(jìn)列表的最后一個(gè)位置，列表容量減一，然后對(duì)新的root元素調(diào)用MAX-HEAPIFY。
以以上這道邀請(qǐng)參加聚會(huì)的題目為例。
