一、概念

1. ?Priority Queues：即帶有優(yōu)先級的隊(duì)列（先進(jìn)先出），較好實(shí)現(xiàn)方式：大根堆，或小根堆。

2. ?堆總是滿足下列性質(zhì)：

a. ?堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

b. ?堆總是一棵完全二叉樹。

將根節(jié)點(diǎn)最大的堆叫做大根堆，根節(jié)點(diǎn)最小的堆叫做小根堆（binary min-heap （minimum key is at the root））。

3. ?滿二叉樹與完全二叉樹：

如果一棵二叉樹的結(jié)點(diǎn)要么是葉子結(jié)點(diǎn)，要么它有兩個子結(jié)點(diǎn)，這樣的樹就是滿二叉樹。

若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。

二、堆 -> 數(shù)組

“堆”存儲在數(shù)組中，某個 i（數(shù)組下標(biāo)）節(jié)點(diǎn)的孩子的數(shù)組下標(biāo)為：i * 2，i * 2 + 1，例如：

X ? T O ? G S M N ? ?A E R A I B

1 ? 2 3 ? ? 4 5 6 7 ? ? 8 9 10 11 12 ? ?(數(shù)組下標(biāo)從1開始，也可以從0開始)

三、downheap() 與?upheap()

1. ?downheap() -> O(log n)

刪除 root -> 堆的最后一個節(jié)點(diǎn)替換 root -> "修復(fù)堆"，root如果有必要與"子節(jié)點(diǎn)"交換 -> 被改變的子節(jié)點(diǎn)繼續(xù)"修復(fù)堆"

2.?upheap()-> O(log n)

插入一個節(jié)點(diǎn)到堆的最后 -> ?"修復(fù)堆"，該節(jié)點(diǎn)如果有必要與"父節(jié)點(diǎn)"交換 -> 被改變的父節(jié)點(diǎn)繼續(xù)?"修復(fù)堆"

四、堆 -> 構(gòu)造

1. downheap()?-> O(n)

bottom-up heap construction 自下而上堆的構(gòu)造

自下而上，從右至左的方向，找到第一個“非葉子節(jié)點(diǎn)”，如果有必要與"子節(jié)點(diǎn)"交換（如果左右節(jié)點(diǎn)相等，交換任意一個都可）

即用 downleap() 方法，對每一個子堆

2. upheap()?-> O(n log n)

一個一個節(jié)點(diǎn)增加到堆的最后 -> 用?upheap() 方法"修復(fù)堆"

五、堆排序

堆排序：O(n log n)