原理參考：堆和堆排序原理介紹

堆的基本操作（以最小堆為例）

• 基本數(shù)組的定義

int n; //數(shù)組元素的個(gè)數(shù)
int heap[100005];  //堆數(shù)組

• 向下調(diào)整操作

向下調(diào)整操作一般是針對(duì)一個(gè)節(jié)點(diǎn)而言的码邻，通過對(duì)其進(jìn)行向下調(diào)整介褥，保證其值是其所在的二叉樹中的最小的數(shù)。

//對(duì)輸入的heap數(shù)組在[low, high]范圍內(nèi)向下調(diào)整窍霞，調(diào)整為最小堆，即小的數(shù)在最上面 
void downHeap(int low, int high){
    //i初始化為欲調(diào)整節(jié)點(diǎn)，j為其左孩子 
    int i = low, j = i * 2;
    //如果還存在孩子節(jié)點(diǎn)則一直比較并調(diào)整 
    while(j <= high){
        //如果右孩子存在且值比左孩子還小踢俄，那么就應(yīng)該將右孩子向上調(diào)整 
        if(j + 1 <= high && heap[j+1] < heap[j])
            j = j + 1;
        //當(dāng)孩子的值比欲調(diào)整節(jié)點(diǎn)大時(shí)，則進(jìn)行交換晴及，保證小的數(shù)在上面 
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);
            //繼續(xù)向下調(diào)整 
            i = j;
            j = j * 2;
        }
        //如果欲調(diào)整節(jié)點(diǎn)的值已經(jīng)比孩子都小則結(jié)束調(diào)整 
        else
            break;
    }
}

• 建堆操作

建堆操作則利用向下調(diào)整的方法對(duì)堆數(shù)組的每一個(gè)元素進(jìn)行向下調(diào)整都办，從而使得每一個(gè)節(jié)點(diǎn)都是以其為根結(jié)點(diǎn)的樹中的最小元素。而通過二叉樹我們可以知道虑稼，葉子節(jié)點(diǎn)是沒有孩子的琳钉，因此對(duì)于葉子節(jié)點(diǎn)可以不用再進(jìn)行向下調(diào)整，因此第一個(gè)調(diào)整的節(jié)點(diǎn)則是最后一個(gè)元素的父節(jié)點(diǎn)蛛倦，因?yàn)樗菢渲凶詈笠粋€(gè)還擁有孩子的節(jié)點(diǎn)歌懒。實(shí)現(xiàn)代碼如下：

//建堆操作 
void createHeap(){
    //建堆從最后一個(gè)還具有孩子的節(jié)點(diǎn)開始，依次往前遍歷到根結(jié)點(diǎn)溯壶，到最后便建立了最小堆 
    for(int i = n / 2; i >= 1; i--){
        downHeap(i, n);
    }
}

• 刪除堆頂元素

對(duì)于堆的刪除操作則一般只針對(duì)堆的堆頂元素及皂，而一般不對(duì)其他元素進(jìn)行刪除。對(duì)堆頂元素進(jìn)行刪除時(shí)且改，只需要將堆的最后一個(gè)元素覆蓋堆頂元素然后再進(jìn)行一次向下調(diào)整即可滿足验烧。刪除后的同時(shí)需要將堆的元素個(gè)數(shù)減一。

//刪除堆頂元素 
void deleteHeap(){
    //將堆最后一個(gè)元素覆蓋堆頂元素又跛，再將元素個(gè)數(shù)n簡易 
    heap[1] = heap[n--];
    //從堆頂?shù)蕉炎詈筮M(jìn)行一次向下調(diào)整碍拆，保證刪除后仍是最小堆 
    downHeap(1, n);
} 

• 向堆插入一個(gè)元素

向堆中插入一個(gè)元素和刪除一個(gè)元素則不同，因?yàn)槌绦蝾A(yù)先是不知道這個(gè)元素應(yīng)該放在什么位置的，而如果直接進(jìn)行查找再添加則會(huì)更加的麻煩感混，體現(xiàn)不出堆的一個(gè)優(yōu)勢(shì)端幼。如果說把它放在第一個(gè)元素位置利用向下調(diào)整，仍會(huì)帶來很多麻煩浩习，比如原本的堆頂元素又放到哪里静暂，如果將原本的堆頂元素放到末尾，那豈不是不是最小堆了谱秽？或者將所有元素往后移動(dòng)洽蛀，將插入的元素放到第一個(gè)位置，再調(diào)整疟赊，這不明顯更加復(fù)雜郊供。
因此在插入一個(gè)元素時(shí)，堆中采用向上調(diào)整的方法近哟，而不是向下調(diào)整驮审，首先將插入的元素放入到堆數(shù)組的最后，并將元素個(gè)數(shù)加1吉执，此時(shí)則對(duì)這插入的最后一個(gè)元素進(jìn)行向上調(diào)整疯淫，直到其值比父親節(jié)點(diǎn)大或者到達(dá)了根結(jié)點(diǎn)時(shí)退出。實(shí)現(xiàn)如下：

//對(duì)heap中[low戳玫，high]范圍內(nèi)進(jìn)行向上調(diào)整 
void upHeap(int low, int high){
    //i初始化為欲調(diào)整節(jié)點(diǎn)熙掺，j為其父親節(jié)點(diǎn) 
    int i = high, j = i / 2;
    //當(dāng)未到達(dá)根結(jié)點(diǎn)時(shí)則繼續(xù)操作 
    while(j >= low){
        //如果父親節(jié)點(diǎn)仍然比欲調(diào)整節(jié)點(diǎn)的值大則繼續(xù)向上，因?yàn)樾枰{(diào)整為最小堆 
        if(heap[j] > heap[i]){
            swap(heap[i], heap[j]);
            i = j;
            j = i / 2;
        }
        //比父親節(jié)點(diǎn)值大咕宿，則達(dá)到退出條件 
        else
            break;
    }
}
//插入一個(gè)元素币绩，利用向上調(diào)整方法 
void insert(int x){
    //將新插入的元素放到堆數(shù)組的最后，并將元素個(gè)數(shù)加1 
    heap[++n] = x;
    //放入后進(jìn)行一次向上調(diào)整 
    upHeap(1, n);
}

堆排序（最小堆為例）

有了以上的堆的基本操作之后則可以進(jìn)行堆排序了府阀。對(duì)于堆排序缆镣，此處以最簡單的為例。

首先對(duì)于堆數(shù)組试浙，則是需要用戶進(jìn)行輸入的董瞻，輸入之后，便可以對(duì)每一個(gè)非葉子節(jié)點(diǎn)元素（從最后一個(gè)具有孩子的節(jié)點(diǎn)開始）進(jìn)行一次向下調(diào)整田巴，從而在遍歷之后可以建立一個(gè)最小堆力细。不過這樣之后的數(shù)組并不是有序的，因?yàn)槲覀冎槐ＷC了當(dāng)前節(jié)點(diǎn)的值比孩子結(jié)點(diǎn)的值小固额，而對(duì)于左右孩子結(jié)點(diǎn)的值是沒有順序的，同理的是左右子樹都不是有序的煞聪，不像二叉搜索樹那樣左子樹的值都是比右子樹要小的斗躏。

因此在建立起最小堆之后，我們已知的是堆頂元素是最小的，因此可以依次將堆頂元素取出來啄糙，排成一個(gè)序列那便是有序的了笛臣。而對(duì)于每次取出的操作可以不必再新開一個(gè)數(shù)組，直接在原堆數(shù)組中進(jìn)行操作隧饼，操作方法為：將堆頂元素和堆末尾的元素交換沈堡，然后針對(duì)前n-1個(gè)元素對(duì)交換后的堆頂元素進(jìn)行一次向下調(diào)整，這樣堆頂便是剩下的n-1個(gè)元素中的最小的元素燕雁，而該元素就是所有元素的第二小的元素诞丽。然后依次這樣操作，第二次則將堆頂元素和n-1位置的元素交換再進(jìn)行一次向下調(diào)整（因?yàn)閚位置已經(jīng)放了最小元素拐格，第二次的n-1個(gè)元素中的最小元素則放在n-1位置）僧免。這樣當(dāng)操作到只剩一個(gè)元素便可結(jié)束操作，得到的堆數(shù)組便是降序排列的捏浊，如果需要升序則逆序輸出即可懂衩。示例代碼如下：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>


using namespace std;
int n;
int heap[100005]; 


//對(duì)輸入的heap數(shù)組在[low, high]范圍內(nèi)向下調(diào)整，調(diào)整為最小堆金踪，即小的數(shù)在最上面 
void downHeap(int low, int high){
    //i初始化為欲調(diào)整節(jié)點(diǎn)浊洞，j為其左孩子 
    int i = low, j = i * 2;
    //如果還存在孩子節(jié)點(diǎn)則一直比較并調(diào)整 
    while(j <= high){
        //如果右孩子存在且值比左孩子還小，那么就應(yīng)該將右孩子向上調(diào)整 
        if(j + 1 <= high && heap[j+1] < heap[j])
            j = j + 1;
        //當(dāng)孩子的值比欲調(diào)整節(jié)點(diǎn)大時(shí)胡岔，則進(jìn)行交換法希，保證小的數(shù)在上面 
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);
            //繼續(xù)向下調(diào)整 
            i = j;
            j = j * 2;
        }
        //如果欲調(diào)整節(jié)點(diǎn)的值已經(jīng)比孩子都小則結(jié)束調(diào)整 
        else
            break;
    }
}
//建堆操作 
void createHeap(){
    //建堆從最后一個(gè)還具有孩子的節(jié)點(diǎn)開始，依次往前遍歷到根結(jié)點(diǎn)姐军，到最后便建立了最小堆 
    for(int i = n / 2; i >= 1; i--){
        downHeap(i, n);
    }
}
//堆排序操作 
void heapSort(){
    //首先建立初始最小堆 
    createHeap();
    //從后遍歷每一個(gè)元素铁材，每次將最小元素放入到i位置，這樣第一次最小放到n
    //第二次的最小則放入到n-1奕锌，第三次則會(huì)放入到n-2...... 
    for(int i = n; i > 1; i--){
        swap(heap[i], heap[1]);
        downHeap(1, i-1);
    }
}

//10
//2 8 4 6 1 10 7 3 5 9
int main() {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &heap[i]);
        heapSort();
        for(int i = n; i >= 1; i--)
            printf("%d ", heap[i]);
    }
    return 0;
}

練習(xí)題目：堆排序