1.二叉堆的定義
最大堆：
除了根結點外着茸，所有的結點都要滿足壮锻，A[PARENT(i)] >= A[i]
最小堆：
除了根結點外，所有的結點都要滿足,A[PARENT(i)]<=A[i]
2.堆的屬性
- 結點的高度
該結點到葉節(jié)點的最長簡單路徑上邊的數(shù)目 - 結點的深度
該結點到根節(jié)點的簡單路徑上邊的數(shù)目
3.堆的應用
3.1堆排序
- 堆排序中的幾個基本過程（以最大堆為例）
MAX-HEAPIFY: 時間復雜度為O(lgn)
BUILD-MAX-HEAP: 構造最大堆涮阔，具有線性時間復雜度
HEAP-SORT: 堆排序猜绣，時間復雜度為O(nlgn) - 堆排序過程
構造堆：
從第一個非葉結點開始（A[A.length/2]），逐步調(diào)用MAX-HEAPIFY(A, i)過程
調(diào)整堆：
交換堆頂元素和堆的最后一個元素敬特，調(diào)用MAX-HEAPIFY(A, i)過程掰邢，循環(huán)n次
3.2實現(xiàn)優(yōu)先隊列
最大（小）堆具有很多很好的特性伟阔，比如：
- 可以直接使用數(shù)組存儲辣之，并且能夠保證平衡性
- 插入刪除操作都具有良好的性能
- 可以在O(1)的時間內(nèi)找到最大（最小）結點
實現(xiàn)優(yōu)先隊列的幾個重要的過程（以最大優(yōu)先隊列為例）：
- INSERT(S,x)
- MAXIMUM(s)
- EXTRACT-MAX(S)
- INCREASE-KEY(S,x,k)
EXTRACT-MAX過程皱炉，類似于堆排序中for循環(huán)內(nèi)的操作怀估，先交換，再從上往下調(diào)整,時間復雜度為O(lgn)
INCREASE-KEY過程合搅，沿著當前結點往上不斷比較多搀，時間復雜度為O(lgn)
INSERT過程，先在尾部新建一個結點灾部，然后調(diào)用INCREASE-KEY過程
