一：什么是堆？
0.優(yōu)先隊(duì)列(Priority Queue)：特殊的“隊(duì)列”毒费，取出元素的順序是依照元素的優(yōu)先權(quán)（關(guān)鍵字）大小验懊，而不是元素進(jìn)入隊(duì)列的現(xiàn)后順序擅羞。
那么問題來了，如何組織有點(diǎn)隊(duì)列呢义图？
<1>:一般的數(shù)組减俏、鏈表？
<2>:有序的數(shù)組或者鏈表碱工？
<3>:二叉搜索樹娃承？AVL樹？
1.如果采用數(shù)組或鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列
<1>:數(shù)組：
插入---元素總是插入尾部? ? ---O(1)
刪除---查找最大（最信屡瘛）關(guān)鍵字? ---O(n),? ? 從數(shù)組種刪去需要移動元素 ---- O(n)
<2>:鏈表：
插入---元素總是插入鏈表的頭部? ?---O（1）
刪除---查找最大（最欣荨）關(guān)鍵字 ---O（n），刪去節(jié)點(diǎn)O（1）
<3>:有序數(shù)組：
插入---找到合適的位置廊谓，---O（n）or O（logN）梳猪，移動元素并插入---O（n）
刪除---刪去最后一個(gè)元素? ?---O（1）
<4>:有序鏈表:
插入---找到合適位置 ---O（n），插入元素 ---O（1）
刪除---刪除首元素或最后元素 ----O（1）
2.是否可以采用二叉樹存儲結(jié)構(gòu)蒸痹？
3.堆的抽象數(shù)據(jù)類型描述：
類型名稱：最大堆（MaxHeap）
數(shù)據(jù)對象集：完全二叉樹春弥、每個(gè)節(jié)點(diǎn)元素不小于其子節(jié)點(diǎn)的元素值。
操作集：最大堆
MaxHeap Create(int MaxSize):創(chuàng)建一個(gè)空的最大堆
bool IsFull(MaxHeap H)：判斷最大堆H是否已滿
void Insert(MaxHeap H, ElementType item):將元素item插入最大堆H
bool IsEmpty(MaxHeap H):判斷最大堆H是否為空
ElementType DeleteMax(MaxHeap H)：返回H中的最大元素（高優(yōu)先級）
<1>:最大對的建立(重點(diǎn)，單獨(dú)放出來進(jìn)行描述)
建立最大堆：將已經(jīng)存在的N個(gè)元素按最大堆的要求存放到一個(gè)一維數(shù)組中者娱。
方法1：通過插入操作抡笼，將N個(gè)元素一個(gè)個(gè)相繼插入一個(gè)初始為空的堆中去，其時(shí)間代價(jià)最大為O(NlogN)
方法2：在線性事件復(fù)雜度下建立最大堆黄鳍。O(n)
{1}：將N個(gè)元素按輸入順序存入推姻，先滿足二叉樹的結(jié)構(gòu)特性
{2}：調(diào)整各節(jié)點(diǎn)位置，以滿足最大堆的有序特性
（1）：方法一的非常的簡單明了际起，也很容易進(jìn)行拾碌，但時(shí)間復(fù)雜度相對較低吐葱，這里就不再綴敘街望。
（2）：對于第二種情況，我們只講解一下通過AVL的鏈表和數(shù)組表現(xiàn)形式來表現(xiàn)的弟跑。對于其他幾種情況并不適用灾前！
其實(shí)，此時(shí)構(gòu)建堆的的思路很簡單孟辑，就是將一個(gè)無序的完全二叉樹調(diào)整為一個(gè)二叉堆哎甲，本質(zhì)就是讓所有的非葉子節(jié)點(diǎn)依次下沉蔫敲。
具體就是：從最后一個(gè)非葉子節(jié)點(diǎn)以知道根節(jié)點(diǎn)進(jìn)行堆化的調(diào)整。如果當(dāng)前節(jié)點(diǎn)小于有個(gè)自己的孩子節(jié)點(diǎn)時(shí)炭玫，那么當(dāng)前節(jié)點(diǎn)和這個(gè)子節(jié)點(diǎn)進(jìn)行交換奈嘿。
問題是，如何找到第一個(gè)非葉子節(jié)點(diǎn)吞加？
我們構(gòu)建二叉堆時(shí)裙犹，根節(jié)點(diǎn)通常是從1的索引開始的，所以第一個(gè)非葉子節(jié)點(diǎn)的計(jì)算為：MaxHeap->size / 2衔憨。如果根節(jié)點(diǎn)在數(shù)組中的索引為0叶圃，那么第一個(gè)非葉子節(jié)點(diǎn)的計(jì)算公式為: last_non_leav = (arr.length - 2)/2〖迹可以設(shè)最后一個(gè)非葉子節(jié)點(diǎn)位置為x掺冠，那么最后一個(gè)葉子節(jié)點(diǎn)一定是(2x+1) 或者(2x+2)中的一個(gè)，然后可以建立方程求解码党。
不知道有沒有細(xì)心的小伙伴發(fā)現(xiàn)這個(gè)Adjust函數(shù)的小錯誤呢接癌？hhh，我更正在下面了扣讼，如果還沒明白的話缺猛，可以發(fā)郵件和我交流，hhh椭符。
