堆的定義

    n個元素的序列{k1，k2祝钢，…, kn} 當(dāng)且僅當(dāng)滿足下列關(guān)系之一時，稱之為堆催跪。
　　情形1：ki <= k2i 且ki <= k2i+1（**最小化堆**或**小頂堆**）
　　情形2：ki>= k2i且ki>= k2i+1（**最****大****化堆**或**大頂堆**）
　　其中i=1,2,…,n/2向下取整;

概念

若將和此序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明夷野，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左懊蒸、右孩子結(jié)點的值。
　　由此悯搔，若序列{k1骑丸，k2，…,kn}是堆妒貌，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）通危。
　　例如，下列兩個序列為堆灌曙，對應(yīng)的完全二叉樹如圖：

圖片.png

堆的存儲

一般用數(shù)組來表示堆魄幕，若根結(jié)點存在序號0處， i結(jié)點的父結(jié)點下標(biāo)就為(i-1)/2颖杏。i結(jié)點的左右子結(jié)點下標(biāo)分別為2i+1和2i+2纯陨。
　　（注：如果根結(jié)點是從1開始输玷，則左右孩子結(jié)點分別是2i和2i+1队丝。）
　　如第0個結(jié)點左右子結(jié)點下標(biāo)分別為1和2。
　　如最大化堆如下：
　　

左圖為其存儲結(jié)構(gòu)欲鹏，右圖為其邏輯結(jié)構(gòu)机久。

堆排序的實現(xiàn)

在輸出堆頂元素之后，視為將這個元素排除赔嚎，然后用表中最后一個元素填補(bǔ)它的位置膘盖，自上向下進(jìn)行調(diào)整：首先將堆頂元素和它的左右子樹的根結(jié)點進(jìn)行比較，把最小的元素交換到堆頂尤误；然后順著被破壞的路徑一路調(diào)整下去侠畔，直至葉子結(jié)點，就得到新的堆损晤。
我們稱這個自堆頂至葉子的調(diào)整過程為“篩選”软棺。
從無序序列建立堆的過程就是一個反復(fù)“篩選”的過程。

構(gòu)造初始堆

初始化堆的時候是對所有的非葉子結(jié)點進(jìn)行篩選尤勋。
最后一個非終端元素的下標(biāo)是[n/2]向下取整喘落，所以篩選只需要從第[n/2]向下取整個元素開始茵宪，從后往前進(jìn)行調(diào)整。
比如瘦棋，給定一個數(shù)組稀火，首先根據(jù)該數(shù)組元素構(gòu)造一個完全二叉樹。
然后從最后一個非葉子結(jié)點開始赌朋，每次都是從父結(jié)點凰狞、左孩子、右孩子中進(jìn)行比較交換沛慢，交換可能會引起孩子結(jié)點不滿足堆的性質(zhì)赡若，所以每次交換之后需要重新對被交換的孩子結(jié)點進(jìn)行調(diào)整。

進(jìn)行堆排序

有了初始堆之后就可以進(jìn)行排序了颠焦。
堆排序是一種選擇排序斩熊。建立的初始堆為初始的無序區(qū)。
排序開始伐庭，首先輸出堆頂元素（因為它是最值）粉渠，將堆頂元素和最后一個元素交換，這樣圾另，第n個位置（即最后一個位置）作為有序區(qū)霸株，前n-1個位置仍是無序區(qū)，對無序區(qū)進(jìn)行調(diào)整集乔，得到堆之后去件，再交換堆頂和最后一個元素，這樣有序區(qū)長度變?yōu)?扰路。尤溜。。
不斷進(jìn)行此操作汗唱，將剩下的元素重新調(diào)整為堆宫莱，然后輸出堆頂元素到有序區(qū)。每次交換都導(dǎo)致無序區(qū)-1哩罪，有序區(qū)+1授霸。不斷重復(fù)此過程直到有序區(qū)長度增長為n-1，排序完成际插。

堆排序?qū)嵗?/h3>

首先碘耳，建立初始的堆結(jié)構(gòu)如圖：
　　

　　然后，交換堆頂?shù)脑睾妥詈笠粋€元素框弛，此時最后一個位置作為有序區(qū)（有序區(qū)顯示為黃色）辛辨，然后進(jìn)行其他無序區(qū)的堆調(diào)整，重新得到大頂堆后，交換堆頂和倒數(shù)第二個元素的位置……
　　

　　重復(fù)此過程：
　　

最后愉阎，有序區(qū)擴(kuò)展完成即排序完成：
　　

由排序過程可見绞蹦，若想得到升序力奋，則建立大頂堆榜旦，若想得到降序，則建立小頂堆景殷。
代碼
　　假設(shè)排列的元素為整型溅呢，且元素的關(guān)鍵字為其本身。
　　因為要進(jìn)行升序排列猿挚，所以用大頂堆咐旧。
　　根結(jié)點從0開始，所以i結(jié)點的左右孩子結(jié)點的下標(biāo)為2i+1和2i+2绩蜻。

算法描述

//堆賽選函數(shù)
//已知H[start-end]中除了start之外均滿足堆的定義
//本函數(shù)進(jìn)行調(diào)整铣墨，使H[start-end]成為一個大頂堆
typedef int ElemType;
void HeapAdjust(ElemType H[], int start, int end) {
    ElemType temp = H[start];
    for (int i = 2 * start + 1; i <= end; i *= 2) {
        //因為根節(jié)點的序號為0 而不是1  所以i結(jié)點左孩子和右孩子分別為2i+1和2i+2
        if (i < end && H[i] < H[i + 1]) {
            //左右孩子進(jìn)行比較
            ++i;//i為較大記錄的下標(biāo)
        }
        if (temp > H[i]) {
            //左右孩子中獲勝者與父親的比較
            break;
        }
        //將孩子結(jié)點上位，則以孩子結(jié)點的位置進(jìn)行下一輪的賽選
        H[start] = H[i];
        start = i;
    }
    H[start] = temp;//插入最開始不和諧的元素
}

void HeapSort(ElemType A[], int n) {
    //先建立大頂堆
    for (int i = n/2; i >= 0; --i) {
        HeapAdjust(A, i, n);
    }
    //進(jìn)行排序
    for (int i = n - 1; i > 0; --i) {
        //最后一個元素和第一個元素進(jìn)行比較
        ElemType temp = A[i];
        A[i] = A[0];
        A[0] = temp;
        //然后將剩下的無序元素繼續(xù)調(diào)整為大頂堆
        HeapAdjust(A, 0, i - 1);
    }
}

int main() {
    int a[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    int len = sizeof(a)/sizeof(int);
    HeapSort(a, len);
    for (int i = 0; i < len; i++) {
        printf("%d\n", a[i]);
    }
    return 0;
}

算法穩(wěn)定性

不穩(wěn)定

算法分析

時間復(fù)雜度： O(nlogn)