堆的定義
? 堆是一個完全二叉樹
–所有葉子在同一層或者兩個連續層
–最后一層的結點占據盡量左的位置
? 堆性質
–為空, 或者最小元素在根上
–兩棵子樹也是堆
存儲方式
? 最小堆的元素保存在heap[1..hs]內
– 根在heap[1]
–K的左兒子是2k, K的右兒子是2k+1,
–K的父親是[k/2]
刪除最小值元素
? 三步法
– 直接刪除根
– 用最后一個元素代替根上元素
– 向下調整
? 首先選取當前結點p的較小兒子，如果比p大, 調整停止；否則交換p和兒子, 繼續調整
插入元素和向上調整
? 插入元素是先添加到末尾, 再向上調整
? 向上調整: 比較當前結點p和父親, 如果父親比p小，停止; 否則交換父親和p, 繼續調整
堆的建立（堆的構造）
1、自底向上堆構造算法：
在初始化一棵包含幾個節點的完全二叉樹時，按給定的順序來效置鍵；然后按照下面的方法對樹進行“堆化”（如下圖）從最后的父母節點開始，到根為止，該算法檢查這些節點的鍵是否滿足父母優勢要求。如果該節點不滿足，該算法把節點的鍵k和它子女的最大鍵進行交換，然后再檢查在新位置上，k是不是滿足父母優勢要求。這個過程一直繼續到對k的父母優勢要求滿足為止，對于以當前父母節點為根的子樹，在完成了它“堆化”以后，該算法對于該節點的直接前趨進行同樣的操作。在對樹的根完成了這種操作以后，該算法就停止了。 ? ?
?
2、自頂向下堆構造算法：
通過把新的鍵連續插入預先構造好的堆，來構造一個新堆，如何把一個新的鍵k插入到堆中呢？首先，把一個包含鍵k的新節點附加在當前堆的最后一個葉子后面，然后按照下面的方法把k篩選到它的適當位置，拿k和它父母的鍵作比較，如果后者大于等于k，算法停止；否則，交換這兩個鍵并把k和它的新父母做比較。這種交換一直持續到k不大于它的最后一個父母，或者是達到了樹的根為止（如下圖）。在這個算法中，我們也可以把一個空節點向上篩選，直到達到合適的位置，才把k的值賦予它。
顯然，這個插入操作所需的鍵值比較次數不可能超過堆的高度。因為包含幾個節點的堆的高度大約是log2n所以插入的時間效率屬于o（logn）。
刪除堆中某個元素（不一定是堆頂元素）
1、以堆中最后一個元素取代被刪除元素留下的空位（此舉確保堆首先是一個完全二叉樹）。
2、堆調整（堆化）。
時間復雜度分析
? 向上調整/向下調整
– 每層是常數級別, 共logn層, 因此為：O(logn)
? 插入/刪除
– 只調用一次向上或向下調整, 因此都是：O(logn)
? 建堆
– 高度為h的結點有n/2h+1個,總時間為：O(n*logn)
【堆，這種數據結構適合解決何種類型的問題？】
？？？........
D$#@&(<):>M"|{_#!@SAQ$&GBD^KFG(*&$#$BK}{?<:>"X~@^
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【堆排序實踐】
輸入n個整數（ n <= 10^5），按從大到小排序后輸出。
操作步驟：
1) 建立堆。（直接在待排序數據A[]上建立最大堆）
2) 重復調整堆。取出堆首元素（根元素），交換至堆尾部，堆容量減1，繼續調整。
優秀范例代碼展示（構架清晰、代碼簡潔、高效！）
輸入輸出格式
輸入格式：
二行，第一行，一個整數值n（ n <= 10^5 ）；第二行，n個整數，每個整數均小于2^31，每個整數間有一個空格間隔。
輸出格式：
一行，排好序（從大到小的順序！！）的n個數據，每個數據間用一個空格間隔。
輸入輸出樣例
輸入樣例#1：
4
4 5 2 897
輸出樣例#1：
897 5 4 2
提示信息
如果僅僅為了AC，那么排序吧！
sort也有一定概率堆排
#include<bits/stdc++.h>
#define sp sort
using namespace std;
int n,a[100010];
int cmp(int x,int y)
{return x>y;
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sp(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}
