定義：堆是一棵完全二叉樹，樹中陪你過每個(gè)結(jié)點(diǎn)的值都不小于（或都不大于）其左右孩子結(jié)點(diǎn)的值。其中，如果父親結(jié)點(diǎn)的值大于或等于孩子結(jié)點(diǎn)的值，那么稱這樣的堆為大頂堆，這時(shí)每個(gè)結(jié)點(diǎn)的值都是以它為根結(jié)點(diǎn)的子樹的最大值；如果父親結(jié)點(diǎn)的值小于或等于孩子節(jié)點(diǎn)的值，那么稱這樣的堆為小頂堆，這是每個(gè)結(jié)點(diǎn)的值都是以它為根結(jié)點(diǎn)的子樹的最小值。堆一般用于優(yōu)先隊(duì)列的實(shí)現(xiàn)，而優(yōu)先隊(duì)列默認(rèn)情況下使用的是大頂堆，因此本屆以大頂堆為例，以下出現(xiàn)的堆均指大頂堆。

結(jié)點(diǎn)按層序儲存于數(shù)組中，其中第一個(gè)結(jié)點(diǎn)將存儲于數(shù)組中的1號位，并且數(shù)組i號位表示結(jié)點(diǎn)的左孩子就是2i號位，而右孩子則是(2i + 1)號位。
定義數(shù)組來表示堆:

const int maxn = 100;
//heap為堆，n為元素個(gè)數(shù)
int heap[maxn], n = 10;

每次調(diào)整都是把結(jié)點(diǎn)從上往下的調(diào)整。針對這種向下調(diào)整，調(diào)整方法是這樣的：總是將當(dāng)前結(jié)點(diǎn)V與它的左右孩子比較（如果有的話），假如孩子中存在權(quán)值比結(jié)點(diǎn)V的權(quán)值大的，就將其中權(quán)值最大的那個(gè)孩子結(jié)點(diǎn)與結(jié)點(diǎn)V交換；交換完畢后繼續(xù)讓結(jié)點(diǎn)V和孩子比較，直到結(jié)點(diǎn)V的孩子的權(quán)值都比結(jié)點(diǎn)V的權(quán)值小或是結(jié)點(diǎn)V不存在孩子結(jié)點(diǎn)。

//對heap數(shù)組在[low, high]范圍向下調(diào)整
//其中l(wèi)ow為欲調(diào)整結(jié)點(diǎn)的數(shù)組下標(biāo)，high一般為堆的最后一個(gè)元素的數(shù)組下標(biāo)
void downAdjust(int low, int high) {
    int i = low, j = i * 2;     //i為欲調(diào)整結(jié)點(diǎn)，j為其左孩子
    while(j <= high) {      //存在孩子結(jié)點(diǎn) 
        //如果右孩子存在，且右孩子的值大于左孩子
        if(j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        //如果孩子中最大的權(quán)值比欲調(diào)整結(jié)點(diǎn)i大
        if(heap[j] > heap[i]) {
            swap(heap[j], heap[i]);     //交換最大權(quán)值的孩子與欲調(diào)整結(jié)點(diǎn)i
            i = j;      //保持i為欲調(diào)整結(jié)點(diǎn)、j為i的左孩子 
            j = i * 2; 
        } else {
            break;      //孩子的權(quán)值比欲調(diào)整結(jié)點(diǎn)i小，調(diào)整結(jié)束 
        }
    } 
} 

這種建堆的做法保證每個(gè)結(jié)點(diǎn)都是以其為根結(jié)點(diǎn)的子樹中的權(quán)值最大的結(jié)點(diǎn)

//建堆
void createHeap() {
    for(int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
} 

如果要?jiǎng)h除堆中的最大元素（也就是刪除堆頂元素），并讓其仍然保持堆的結(jié)構(gòu)，那么只需要最后一個(gè)元素覆蓋堆頂元素，然后對根結(jié)點(diǎn)進(jìn)行調(diào)整即可。

//刪除堆頂元素
void deleTop() {
    heap[1] = heap[n--];    //用最后一個(gè)元素覆蓋堆頂元素，并讓元素個(gè)數(shù)減一
    downAdjust(1, n);      //向下調(diào)整堆頂元素
}

添加一個(gè)元素，可以把想要添加的元素放在數(shù)組最后（也就是完全二叉樹的最后一個(gè)結(jié)點(diǎn)后面），然后進(jìn)行向上調(diào)整操作。向上調(diào)整總是把欲調(diào)整結(jié)點(diǎn)與父親結(jié)點(diǎn)比較，如果權(quán)值比父親結(jié)點(diǎn)大，那么就交換其與父親結(jié)點(diǎn)，這樣反復(fù)比較，直到達(dá)堆頂或是父親結(jié)點(diǎn)的權(quán)值較大為止。向上調(diào)整代碼如下：

//對heap數(shù)組在[low, high]范圍進(jìn)行向上調(diào)整
//其中l(wèi)ow一般設(shè)置為1,high表示欲調(diào)整結(jié)點(diǎn)的數(shù)組下標(biāo)
void upAdjust(int low, int high) {
    int i = high, j = i / 2;        //i為欲調(diào)整結(jié)點(diǎn)，j為其父親
    while(j >= low) {
        //父親權(quán)值小于欲調(diào)整結(jié)點(diǎn)i的權(quán)值
        if(heap[j] < heap[i]) {
            swap(heap[j], heap[i]);
            i = j;
            j = i / 2;
        } else { 
            break;
        }
    } 
}

添加元素的代碼

//添加元素x
void insert(int x) {
    heap[++n] = x;
    upAdjust(1, n);
} 

堆排序

堆排序是指使用對結(jié)構(gòu)對一個(gè)序列進(jìn)行排序。此處討論遞增排序的情況
考慮對一個(gè)堆來說，堆頂元素是最大的，因此在建堆完畢后，堆排序的直觀思路就是取出堆頂元素，然后將堆的最后一個(gè)元素替換至堆頂，再進(jìn)行一次針對堆頂元素的向下調(diào)整——如此重復(fù)，直到堆中只有一個(gè)元素為止。
具體實(shí)現(xiàn)時(shí)，為了節(jié)省空間，可以倒著遍歷數(shù)組，假設(shè)當(dāng)前訪問到i號位，那么將堆頂元素與i號位的元素交換，接著在[1, i - 1]范圍內(nèi)對堆頂元素進(jìn)行一次向下調(diào)整即可。

void heapSort() {
    createHeap();       //建堆
    for(int i = n; i > 1; i--) {    //倒著枚舉，直到堆中只有一個(gè)元素 
        swap(heap[i], heap[1]);     //交換heap[i]與堆頂 
        downAdjust(1, i - 1);       //調(diào)整堆頂 
    }   
}