一：什么是堆？
0.優(yōu)先隊列(Priority Queue)：特殊的“隊列”，取出元素的順序是依照元素的優(yōu)先權（關鍵字）大小，而不是元素進入隊列的現后順序。
那么問題來了，如何組織有點隊列呢？
<1>:一般的數組、鏈表？
<2>:有序的數組或者鏈表？
<3>:二叉搜索樹？AVL樹？
1.如果采用數組或鏈表實現優(yōu)先隊列
<1>:數組：
插入---元素總是插入尾部? ? ---O(1)
刪除---查找最大（最?。╆P鍵字? ---O(n),? ? 從數組種刪去需要移動元素 ---- O(n)
<2>:鏈表：
插入---元素總是插入鏈表的頭部? ?---O（1）
刪除---查找最大（最?。╆P鍵字 ---O（n），刪去節(jié)點O（1）
<3>:有序數組：
插入---找到合適的位置，---O（n）or O（logN），移動元素并插入---O（n）
刪除---刪去最后一個元素? ?---O（1）
<4>:有序鏈表:
插入---找到合適位置 ---O（n），插入元素 ---O（1）
刪除---刪除首元素或最后元素 ----O（1）
2.是否可以采用二叉樹存儲結構？
3.堆的抽象數據類型描述：
類型名稱：最大堆（MaxHeap）
數據對象集：完全二叉樹、每個節(jié)點元素不小于其子節(jié)點的元素值。
操作集：最大堆
MaxHeap Create(int MaxSize):創(chuàng)建一個空的最大堆
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>:最大對的建立(重點，單獨放出來進行描述)
建立最大堆：將已經存在的N個元素按最大堆的要求存放到一個一維數組中。
方法1：通過插入操作，將N個元素一個個相繼插入一個初始為空的堆中去，其時間代價最大為O(NlogN)
方法2：在線性事件復雜度下建立最大堆。O(n)
{1}：將N個元素按輸入順序存入，先滿足二叉樹的結構特性
{2}：調整各節(jié)點位置，以滿足最大堆的有序特性
（1）：方法一的非常的簡單明了，也很容易進行，但時間復雜度相對較低，這里就不再綴敘。
（2）：對于第二種情況，我們只講解一下通過AVL的鏈表和數組表現形式來表現的。對于其他幾種情況并不適用！
其實，此時構建堆的的思路很簡單，就是將一個無序的完全二叉樹調整為一個二叉堆，本質就是讓所有的非葉子節(jié)點依次下沉。
具體就是：從最后一個非葉子節(jié)點以知道根節(jié)點進行堆化的調整。如果當前節(jié)點小于有個自己的孩子節(jié)點時，那么當前節(jié)點和這個子節(jié)點進行交換。
問題是，如何找到第一個非葉子節(jié)點？
我們構建二叉堆時，根節(jié)點通常是從1的索引開始的，所以第一個非葉子節(jié)點的計算為：MaxHeap->size / 2。如果根節(jié)點在數組中的索引為0，那么第一個非葉子節(jié)點的計算公式為: last_non_leav = (arr.length - 2)/2?？梢栽O最后一個非葉子節(jié)點位置為x，那么最后一個葉子節(jié)點一定是(2x+1) 或者(2x+2)中的一個，然后可以建立方程求解。
不知道有沒有細心的小伙伴發(fā)現這個Adjust函數的小錯誤呢？hhh，我更正在下面了，如果還沒明白的話，可以發(fā)郵件和我交流，hhh。
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。
