1. 堆的基礎(chǔ)知識(shí)

1.1 什么是堆

堆是一種特殊的二叉樹(shù)，它需要滿足如下兩個(gè)條件

1. 堆是一顆完全二叉樹(shù)
2. 堆中每個(gè)節(jié)點(diǎn)的值都大于或等于（小于或等于）它的子節(jié)點(diǎn)的值

我們把每個(gè)節(jié)點(diǎn)都大于或等于它的子節(jié)點(diǎn)的值的對(duì)叫做大頂堆；每個(gè)節(jié)點(diǎn)的值都小于等于它的子節(jié)點(diǎn)的堆叫做小頂堆。

上面圖中這幾顆樹(shù)，第1個(gè)和第2個(gè)是大頂堆，第3個(gè)是小頂堆，第4個(gè)不是堆，它不是一顆完全二叉樹(shù)

1.2 堆的存儲(chǔ)

根據(jù)堆是一顆完全二叉樹(shù)的特性，所以我們可以使用數(shù)組來(lái)存儲(chǔ)堆。

假如我們從數(shù)組的下標(biāo)1開(kāi)始存儲(chǔ)，則如圖的這樣一個(gè)堆對(duì)應(yīng)的存儲(chǔ)如圖中數(shù)組

從數(shù)組下標(biāo)為1的位置開(kāi)始存儲(chǔ)，完全二叉樹(shù)的節(jié)點(diǎn)關(guān)系

1. 下標(biāo)為i的節(jié)點(diǎn)的左孩子的下標(biāo)就是i*2
2. 下標(biāo)為i的節(jié)點(diǎn)的右孩子的下標(biāo)就是i*2+1

根據(jù)完全二叉樹(shù)的特性，最后一個(gè)非葉子節(jié)點(diǎn)是第n/2個(gè)節(jié)點(diǎn)，這里從數(shù)組下標(biāo)1開(kāi)始存儲(chǔ)，所以最后一個(gè)非葉子節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)就是n/2。第1到第n/2個(gè)節(jié)點(diǎn)是非葉子結(jié)點(diǎn)，第n/2+1到第n個(gè)節(jié)點(diǎn)是葉子結(jié)點(diǎn)。

1.3 堆的常見(jiàn)操作

堆中常見(jiàn)的操作有:插入一個(gè)元素、刪除堆頂元素

1.3.1 插入一個(gè)元素

插入一個(gè)元素可以將要插入的元素放到堆的最后面，然后對(duì)這個(gè)元素采用自下而上的方式來(lái)進(jìn)行堆化

將插入的元素放到堆的最后的示意圖

插入一個(gè)元素的堆化過(guò)程就是沿著節(jié)點(diǎn)所在的路徑，自下而上和父節(jié)點(diǎn)比較大小，如果父子節(jié)點(diǎn)之間不滿足大小關(guān)系，則交換兩個(gè)節(jié)點(diǎn)的位置，然后繼續(xù)拿著插入節(jié)點(diǎn)和新的父節(jié)點(diǎn)比較，直到滿足大小關(guān)系或者插入節(jié)點(diǎn)已經(jīng)是堆頂元素了

插入元素的堆化過(guò)程示意圖

1.3.2 刪除堆頂元素

刪除堆頂元素，我們采用使用堆中最后一個(gè)元素來(lái)替代堆頂元素，然后對(duì)新的堆頂元素自頂向下的堆化的方式來(lái)實(shí)現(xiàn)

刪除堆頂元素的過(guò)程（我們以維護(hù)一個(gè)大頂堆來(lái)講解）：第一步，拿堆中最后一個(gè)元素替換掉堆頂元素；第二步：比較新的堆頂元素和它的左右孩子中值較大的孩子之間的大小，如果不滿足大小關(guān)系，則交換堆頂元素與值較大的孩子之間的位置，然后拿著剛才那個(gè)堆頂元素和它新的左右孩子中的值較大的孩子比較，重復(fù)這個(gè)過(guò)程，直到滿足大小關(guān)系或者新的堆頂元素已經(jīng)交換到了葉子節(jié)點(diǎn)的位置

刪除堆頂元素的堆化過(guò)程示意圖

1.4 如何創(chuàng)建一個(gè)堆

創(chuàng)建一個(gè)堆有兩種思路

1. 第一種是借助前面講的，在堆中插入一個(gè)元素的思路。我們假設(shè)起始堆中只包含一個(gè)數(shù)據(jù)，就是下標(biāo)為1的數(shù)據(jù)，然后我們調(diào)用前面講的插入操作，將下標(biāo)為2到n的數(shù)據(jù)依次插入到堆中。這樣我們就將包含n個(gè)數(shù)據(jù)的數(shù)組，組織成了堆。
2. 第二種實(shí)現(xiàn)思路，跟第一種截然相反。第一種建堆思路的處理過(guò)程是從前往后處理數(shù)據(jù)，并且每個(gè)數(shù)據(jù)插入堆中時(shí)，都是從下往上堆化。第二種實(shí)現(xiàn)思路，是從后往前處理數(shù)據(jù)，并且每個(gè)數(shù)據(jù)都是從上往下堆化。具體實(shí)現(xiàn)就是從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，依次堆化每個(gè)非葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都從上往下完成堆化

下面我們看一個(gè)堆化過(guò)程演示，我們依次對(duì)8,19,5,7四個(gè)非葉子節(jié)點(diǎn)進(jìn)行了從上到下的堆化

堆化過(guò)程示意圖

代碼實(shí)現(xiàn)

public static void createHeap(int[] a, int n) {
    /**
     * 構(gòu)建過(guò)程：從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，從后往前，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行自上而下的堆化
     */
    for (int i = n / 2; i >= 1; i--) {
        heapify(a, n, i);
    }
}

/**
 * 堆化根節(jié)點(diǎn)：找出當(dāng)前節(jié)點(diǎn)的左右孩子中較大的一個(gè)，和根節(jié)點(diǎn)比較，符合順序則結(jié)束；不符合順序，則交換并繼續(xù)比較
 *
 * @param a
 * @param n
 * @param i
 */
private static void heapify(int[] a, int n, int i) {
    int current = i;
    while (true) {
        int maxPos = -1;
        int left = current * 2;//左孩子的位置
        int right = left + 1;//右孩子的位置
        if (right <= n) {
            if (a[left] < a[right]) {
                maxPos = right;
            } else {
                maxPos = left;
            }
        } else if (left <= n) {
            maxPos = left;
        }
        if (maxPos == -1) {//沒(méi)有子孩子
            break;
        }
        if (a[current] >= a[maxPos]) {//根節(jié)點(diǎn)比子孩子大
            break;
        } else {//和子孩子交換位置，繼續(xù)比較
            int temp = a[maxPos];
            a[maxPos] = a[current];
            a[current] = temp;
            current = maxPos;
        }
    }
}

2. 堆的應(yīng)用：堆排序

2.1 如何利用堆進(jìn)行排序

假如我們要進(jìn)行從小到大的排序，那我們先將數(shù)據(jù)建立一個(gè)大頂堆，這樣建堆完成之后，數(shù)組中的數(shù)據(jù)就已經(jīng)是按照大頂堆的特性來(lái)組織的了。數(shù)組中的第一個(gè)元素就是堆頂元素，也就是最大的元素。我們把它和最后一個(gè)元素交換，那最大元素就放到了下標(biāo)為n的位置。

這個(gè)過(guò)程有點(diǎn)類似于“刪除堆頂元素”的操作，當(dāng)堆頂元素移除之后，我們把下標(biāo)為n的元素放到堆頂，然后再通過(guò)堆化的方法，將剩下的n-1個(gè)元素重新構(gòu)建成堆。堆化完成之后，我們?cè)偃《秧斣睾偷趎-1個(gè)元素交換位置，然后再將前面的n-2個(gè)元素堆化，一直重復(fù)這個(gè)過(guò)程，直到最后堆中只剩下下標(biāo)為1的一個(gè)元素，排序工作就完成了。

排序過(guò)程演示圖

代碼實(shí)現(xiàn)

public static void sort(int[] a, int n) {
    //將堆頂元素和最后一個(gè)元素交互位置，然后自上而下堆化前面n-1個(gè)元素；重復(fù)這個(gè)過(guò)程直到堆中只有一個(gè)元素
    if (n == 1) {
        return;
    }
    createHeap(a, n);
    for (int i = n; i >= 2; i--) {
        int temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        heapify(a, i - 1, 1);
    }
}

2.2 堆排序的性能分析

1. 創(chuàng)建堆的性能分析
2. 刪除堆頂元素的性能分析

2.2.1 創(chuàng)建堆的性能分析

堆化過(guò)程中，我們只需要對(duì)第1到n/2個(gè)節(jié)點(diǎn)進(jìn)行堆化。而每個(gè)節(jié)點(diǎn)堆化的過(guò)程中，需要比較和交互的節(jié)點(diǎn)個(gè)數(shù)，跟這個(gè)節(jié)點(diǎn)的高度K成正比

下圖表示了每一層的節(jié)點(diǎn)個(gè)數(shù)和對(duì)
應(yīng)的高度。我們只需要將每個(gè)節(jié)點(diǎn)的高度求和，得出的就是建堆的時(shí)間復(fù)雜度。

節(jié)點(diǎn)層次和高度示意圖

我們將每個(gè)非葉子節(jié)點(diǎn)的高度求和，就是下面的這個(gè)公式

將公式左右兩側(cè)都乘以2，得到另外一個(gè)公司S2，然后將用S2-S1,可以得到S

S的中間部分是一個(gè)等比數(shù)列，所以最后可以用等比數(shù)列求和公式來(lái)計(jì)算，最終的結(jié)果就是下面圖中畫(huà)的這個(gè)樣子。

因?yàn)閔=log2(n),代入公式S，就得到了S=O(n)，所以，建堆的時(shí)間復(fù)雜度就是O(n)

2.2.2 刪除堆頂元素的性能分析

刪除的算法復(fù)雜度推算過(guò)程和建堆的復(fù)雜度推算過(guò)程類似，最后計(jì)算出來(lái)的復(fù)雜度是O(nlogn)。

所以堆排序總的時(shí)間復(fù)雜度是O(nLogn).

源碼

完整的源碼和測(cè)試用例，請(qǐng)查看github之堆和堆排序

說(shuō)明

文中圖片來(lái)源：極客時(shí)間，王爭(zhēng)《數(shù)據(jù)結(jié)構(gòu)與算法之美》