十大排序算法第二彈：從堆到堆排序

一驱闷、何為“堆”

（一）基本概念

1者娱、滿二叉樹

?一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹役衡。也就是說咙轩，如果一個二叉樹的層數(shù)為k眶明，且結(jié)點(diǎn)總數(shù)是(2^k) -1 惩坑，則它就是滿二叉樹。如下圖所示例子：

滿二叉樹

2朝扼、完全二叉樹

?完全二叉樹的結(jié)點(diǎn)數(shù)是任意的赃阀，從形式上講它是個缺失的的三角形，但所缺失的部分一定是右下角某個連續(xù)的部分擎颖，最后那一行可能不是完整的榛斯，對于k層的完全二叉樹，結(jié)點(diǎn)數(shù)的范圍2^(k-1)-1 < N< 2^k – 1搂捧；
?設(shè)二叉樹的深度為h驮俗，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)允跑，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊王凑，這就是完全二叉樹。如下圖所示例子：

完全二叉樹

?有關(guān)二叉樹的知識聋丝，小編并沒有很系統(tǒng)的去總結(jié)索烹，接下來也將做一個深入分享。

（二）堆的定義及其分類

1弱睦、定義

?堆（英語：heap)是計算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱百姓，是一顆完全二叉樹，通常是一個可以被看做一棵樹的數(shù)組對象况木。
?堆是具有以下性質(zhì)的完全二叉樹：
?（1）每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值垒拢，稱為大頂堆；
?（2）每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值火惊，稱為小頂堆子库。

2、二叉堆的分類

（1）大頂堆
?大頂堆中，每個結(jié)點(diǎn)的值都大于其左孩子和右孩子結(jié)點(diǎn)的值。我們來畫個圖演示下：

大頂堆

?對堆中的結(jié)點(diǎn)按層進(jìn)行編號，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子：

大頂堆映射的數(shù)組

（2）小頂堆
?小頂堆中雷袋，每個結(jié)點(diǎn)的值都小于其左孩子和右孩子結(jié)點(diǎn)的值贼陶。同樣給個例子如下：

小頂堆

?對堆中的結(jié)點(diǎn)按層進(jìn)行編號趴樱，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子：

小頂堆映射的數(shù)組

（三）堆結(jié)點(diǎn)訪問

?通常堆是通過一維數(shù)組來實(shí)現(xiàn)的。在數(shù)組起始位置為0的情形中羞福，父結(jié)點(diǎn)和子結(jié)點(diǎn)的位置關(guān)系如下：
?（1）索引為i的左孩子的索引是 (2* i+1)
?（2）索引為i的右孩子的索引是 (2* i+2)
?（3）索引為i的父結(jié)點(diǎn)的索引是 (i -1)/2
?注意：這里得到的關(guān)系由數(shù)組的起始位置來決定液肌。小伙伴們可以對照上述大頂堆和小頂堆的圖來分析分析索引的對應(yīng)關(guān)系额湘。
?因此旁舰，在第一個元素的索引為0時：
?對于大頂堆有：arr(i)>arr(2* i+1) && arr(i)>arr(2* i+2)
?對于小頂堆有：arr(i)<arr(2* i+1) && arr(i)<arr(2* i+2)

二锋华、構(gòu)造初始堆（堆調(diào)整）

?將無序數(shù)組構(gòu)造成一個堆（升序用大頂堆，降序用小頂堆）箭窜。假設(shè)存在以下數(shù)組：

無序數(shù)組

?我們先將它轉(zhuǎn)換成一棵樹毯焕，如下圖所示：

數(shù)組轉(zhuǎn)換成樹結(jié)構(gòu)

?首先，我們找到當(dāng)前這棵樹的最后一個非葉子結(jié)點(diǎn)磺樱，對從該結(jié)點(diǎn)開始的所有非葉子結(jié)點(diǎn)進(jìn)行結(jié)構(gòu)判斷纳猫，并依次進(jìn)行調(diào)整。注意竹捉，這里是自底向上芜辕，從右至左對非葉子結(jié)點(diǎn)進(jìn)行判斷。但對于每個結(jié)點(diǎn)的調(diào)整而言块差，其實(shí)是向下調(diào)整侵续。

（一）調(diào)整成大頂堆

第一步

?找到最后一個非葉子結(jié)點(diǎn)為“數(shù)組長度/2-1=5/2-1=1【索引i=1】”倔丈，也就是上圖中的結(jié)點(diǎn)36。询兴，開始進(jìn)行判斷該子樹是否滿足堆的性質(zhì)乃沙。
?可以發(fā)現(xiàn)以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹不滿足大頂堆的結(jié)構(gòu)，找到子結(jié)點(diǎn)元素最大的那一個【兩個子結(jié)點(diǎn)為arr[i* 2+1]與arr[i* 2+2]诗舰，也就是arr[3]與arr[4]】，進(jìn)行調(diào)整训裆，如下圖所示：

36和47交換

?換下后的結(jié)點(diǎn)屬于葉子結(jié)點(diǎn)眶根，無需再進(jìn)行判斷是否滿足堆的性質(zhì)。

第二步

?繼續(xù)找到上一個非葉子結(jié)點(diǎn)边琉，也就是結(jié)點(diǎn)18【索引i=0】属百，按照相同方法進(jìn)行調(diào)整。

47和18交換

?結(jié)點(diǎn)調(diào)換之后变姨，需要繼續(xù)判斷換下后的結(jié)點(diǎn)是否符合堆的特性【也就是以當(dāng)前結(jié)點(diǎn)18為根的子樹】族扰。發(fā)現(xiàn)不符合，繼續(xù)調(diào)整定欧。此時結(jié)點(diǎn)18的索引i=1渔呵，從其左右孩子結(jié)點(diǎn)中選擇最大的一個進(jìn)行調(diào)換，結(jié)果如下：

40和18交換

第三步

?發(fā)現(xiàn)沒有非葉子結(jié)點(diǎn)了砍鸠，這時調(diào)整結(jié)束扩氢。此時得到的就是最大堆。
?仔細(xì)分析爷辱，發(fā)現(xiàn)可以通過一個外層的循環(huán)從最后一個非葉子結(jié)點(diǎn)開始進(jìn)行遍歷【所有非葉子結(jié)點(diǎn)】录豺，注意這里非葉子結(jié)點(diǎn)的訪問順序是自底向上。循環(huán)體用來判斷是否滿足堆的性質(zhì)來決定是否進(jìn)行調(diào)整饭弓。每次進(jìn)行調(diào)整時需要判斷交換后的結(jié)點(diǎn)是否也滿足堆的性質(zhì)双饥，不滿足要繼續(xù)進(jìn)行同樣的調(diào)整，這里是一個向下調(diào)整的過程弟断∮交ǎ可以發(fā)現(xiàn)這其實(shí)是一個遞歸的過程【當(dāng)然也可以采用迭代的方式實(shí)現(xiàn)】。因此代碼設(shè)計上可以采用“循環(huán)+遞歸”或者“循環(huán)+迭代”的方法夫嗓。

示例代碼如下：

#include<iostream>
using namespace std;
/**
    * 遞歸實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)迟螺，使其符合堆的特性。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
void AdjustDown(int *arr, int index, int len) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int cMax = li;             // 子節(jié)點(diǎn)值最大索引舍咖，默認(rèn)左子節(jié)點(diǎn)矩父。

    // 左子節(jié)點(diǎn)索引超出計算范圍，直接返回排霉。
    if (li > len) 
    {
        return;
    }

    // 先判斷左右子節(jié)點(diǎn)窍株，哪個較大。
    if (ri <= len && arr[li]<arr[ri]) 
    {
        cMax = ri;
    }
    //如果根結(jié)點(diǎn)小于葉子結(jié)點(diǎn)，交換 
    if (arr[index]<arr[cMax]) 
    {
        int item=arr[index];
        arr[index]=arr[cMax];
        arr[cMax]=item;
        AdjustDown(arr, cMax, len);  // 如果父節(jié)點(diǎn)被子節(jié)點(diǎn)調(diào)換球订，則需要繼續(xù)判斷換下后的父節(jié)點(diǎn)是否符合堆的特性后裸。
    }
}

/**
    * 迭代實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性冒滩。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
void maxHeapAdjust(int *arr, int index, int len) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int item=arr[index];      //存儲該索引結(jié)點(diǎn) 
    while(li<len) 
    {
        int cMax = li;             // 子節(jié)點(diǎn)值最大索引微驶，默認(rèn)左子節(jié)點(diǎn)。
        // 先判斷左右子節(jié)點(diǎn)开睡，哪個較大因苹。
        if (ri<=len && arr[li]<arr[ri]) 
        {
            cMax=ri;
        }
        //如果根結(jié)點(diǎn)小于葉子結(jié)點(diǎn)，交換 
        if (item>=arr[cMax]) 
        {
           break;
        }
        arr[li/2]=arr[cMax];//把子節(jié)點(diǎn)值賦值給父結(jié)點(diǎn) 
        li=cMax*2+1;//找到以cMax值為索引的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
        ri=li+1; 
    }
    arr[li/2]=item; //找到正確位置賦值 
}

int main()
{
    int len=15; 
    int arr[len]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    int maxIndex = len - 1; //最大索引 
    int beginIndex = len/ 2 - 1;  //最后一個非葉子結(jié)點(diǎn)索引 
    /*
        *  將數(shù)組堆化
        *  beginIndex = 第一個非葉子節(jié)點(diǎn)篇恒。
        *  從第一個非葉子節(jié)點(diǎn)開始即可扶檐。無需從最后一個葉子節(jié)點(diǎn)開始。
        *  葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)胁艰，根節(jié)點(diǎn)就是它自己且自己以下值為最大款筑。
        *  循環(huán)遍歷 
    */
    for (int i = beginIndex; i >= 0; i--) 
    {
       //maxHeapAdjust(arr, i, maxIndex);
       AdjustDown(arr, i, maxIndex);
    }
    
    for(int i=0;i<len;i++)
    {
        cout<<arr[i]<<"  ";
     } 
     return 0;
}

（二）調(diào)整成小頂堆

?我們來把上述得到的最大堆來調(diào)整成最小堆。也就是下圖：

大頂堆

第一步

?找到最后一個非葉子結(jié)點(diǎn)為“數(shù)組長度/2-1=5/2-1=1【索引i=1】”腾么，也就是上圖中的結(jié)點(diǎn)40奈梳。，開始進(jìn)行判斷該子樹是否滿足堆的性質(zhì)哮翘。
?可以發(fā)現(xiàn)以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹不滿足最小堆的結(jié)構(gòu)颈嚼，找到子結(jié)點(diǎn)元素最小的那一個【兩個子結(jié)點(diǎn)為arr[i* 2+1]與arr[i* 2+2]，也就是arr[3]與arr[4]】饭寺，進(jìn)行調(diào)整阻课，如下圖所示：

40和18交換

?換下后的結(jié)點(diǎn)屬于葉子結(jié)點(diǎn)，無需再進(jìn)行判斷是否滿足堆的性質(zhì)艰匙。

第二步

?繼續(xù)找到上一個非葉子結(jié)點(diǎn)限煞，也就是結(jié)點(diǎn)47【索引i=0】，按照相同方法進(jìn)行調(diào)整员凝。

47和18交換

?結(jié)點(diǎn)調(diào)換之后署驻，需要繼續(xù)判斷換下后的結(jié)點(diǎn)是否符合堆的特性【也就是以當(dāng)前結(jié)點(diǎn)47為根的子樹】。發(fā)現(xiàn)不符合健霹，繼續(xù)調(diào)整旺上。此時結(jié)點(diǎn)47的索引i=1，從其左右孩子結(jié)點(diǎn)中選擇最小的一個進(jìn)行調(diào)換糖埋，結(jié)果如下：

47和36交換

第三步

?發(fā)現(xiàn)沒有非葉子結(jié)點(diǎn)了宣吱，這時調(diào)整結(jié)束。此時得到的就是最大堆瞳别。
?代碼設(shè)計邏輯基本上是一樣的征候。

示例代碼

#include<iostream>
using namespace std;
/**
    * 遞歸實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)杭攻，使其符合堆的特性。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
void AdjustDown(int *arr, int index, int len) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int cMax = li;             // 子節(jié)點(diǎn)值最大索引疤坝，默認(rèn)左子節(jié)點(diǎn)兆解。

    // 左子節(jié)點(diǎn)索引超出計算范圍，直接返回跑揉。
    if (li > len) 
    {
        return;
    }

    // 先判斷左右子節(jié)點(diǎn)锅睛，哪個較小。
    if (ri <= len && arr[ri]<arr[li]) 
    {
        cMax = ri;
    }
    //如果根結(jié)點(diǎn)大于葉子結(jié)點(diǎn)历谍，交換 
    if (arr[index]>arr[cMax]) 
    {
        int item=arr[index];
        arr[index]=arr[cMax];
        arr[cMax]=item;
        AdjustDown(arr, cMax, len);  // 如果父節(jié)點(diǎn)被子節(jié)點(diǎn)調(diào)換衣撬，則需要繼續(xù)判斷換下后的父節(jié)點(diǎn)是否符合堆的特性。
    }
}

/**
    * 迭代實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)扮饶，使其符合堆的特性。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
void maxHeapAdjust(int *arr, int index, int len) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int item=arr[index];      //存儲該索引結(jié)點(diǎn) 
    while(li<len) 
    {
        int cMax = li;             // 子節(jié)點(diǎn)值最大索引乍构，默認(rèn)左子節(jié)點(diǎn)甜无。
        // 先判斷左右子節(jié)點(diǎn)，哪個較小哥遮。
        if (ri<=len && arr[ri]<arr[li]) 
        {
            cMax=ri;
        }
        //如果根結(jié)點(diǎn)小于葉子結(jié)點(diǎn)岂丘，交換 
        if (item<arr[cMax]) 
        {
           break;
        }
        arr[li/2]=arr[cMax];//把子節(jié)點(diǎn)值賦值給父結(jié)點(diǎn) 
        li=cMax*2+1;//找到以cMax值為索引的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
        ri=li+1; 
    }
    arr[li/2]=item; //找到正確位置賦值 
}

int main()
{
    int len=5; 
    int arr[len]={47,40,45,18,36};
    int maxIndex = len - 1; //最大索引 
    int beginIndex = len/ 2 - 1;  //最后一個非葉子結(jié)點(diǎn)索引 
    /*
        *  將數(shù)組堆化
        *  beginIndex = 第一個非葉子節(jié)點(diǎn)。
        *  從第一個非葉子節(jié)點(diǎn)開始即可眠饮。無需從最后一個葉子節(jié)點(diǎn)開始奥帘。
        *  葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)，根節(jié)點(diǎn)就是它自己且自己以下值為最小仪召。
        *  循環(huán)遍歷 
    */
    for (int i = beginIndex; i >= 0; i--) 
    {
       //maxHeapAdjust(arr, i, maxIndex);
       AdjustDown(arr, i, maxIndex);
    }
    
    for(int i=0;i<len;i++)
    {
        cout<<arr[i]<<"  ";
     } 
     return 0;
}

(三)時間復(fù)雜度分析

?假設(shè)二叉樹的高度為k寨蹋，則從倒數(shù)第二層右邊的節(jié)點(diǎn)開始，這一層的節(jié)點(diǎn)都要執(zhí)行子節(jié)點(diǎn)比較然后交換（如果順序是對的就不用交換）扔茅；倒數(shù)第三層呢已旧，則會選擇其子節(jié)點(diǎn)進(jìn)行比較和交換，如果沒交換就可以不用再執(zhí)行下去了召娜。如果交換了运褪，那么又要選擇一支子樹進(jìn)行比較和交換；高層也是這樣逐漸遞歸玖瘸。
?小編來分析下這個時間復(fù)雜度求解的過程秸讹。
?1、n為結(jié)點(diǎn)的個數(shù)雅倒，樹的高度（即堆的高度）為h【樹的高度與深度相等】
?2璃诀、由于是自底向上，從右至左調(diào)整構(gòu)建堆屯断，因此在調(diào)整上層元素的時候文虏，并不需要同下層所有元素進(jìn)行比較侣诺，只需要同其中一個分支進(jìn)行比較，而做比較的次數(shù)則是樹的高度減去當(dāng)前結(jié)點(diǎn)的高度氧秘。第i層上結(jié)點(diǎn)元素的個數(shù)為2^(i-1)年鸳，(h-i)表示每個結(jié)點(diǎn)要比較的次數(shù)。因此丸相，第i層所有結(jié)點(diǎn)的總比較次數(shù)為T(i)=2^(i-1) * (h-i)搔确。
?3、因此灭忠，總的計算時間：
?S=T(h-1)+T(h-2)+……+T(1)=2^(h-2)* 1+2^(h-3)* 2+……+(h-1)
?注意：因?yàn)槿~子層不用交換膳算，所以i從h-1開始到1，第一個非葉子結(jié)點(diǎn)所在層所有結(jié)點(diǎn)的高度都為1弛作。
?可以發(fā)現(xiàn)該數(shù)列為等差數(shù)列和等比數(shù)列的乘積踏兜，利用錯位相減法可進(jìn)行解決。
?2S=2(T(h-1)+T(h-2)+……T(1))=2^(h-1)* 1+2^(h-2)* 2+……+2* (h-1)
?2S-S=2^(h-1)+2^(h-2)+2^(h-3)+……+2-(h-1)
?除最后一項(xiàng)外长酗，這就是個等比數(shù)列纽谒，直接用上求和公式：
?S_n=a1* (1-qⁿ)/(1-q)(q≠1)
?得到：S=2^h-h-1
?因?yàn)閔為完全二叉樹的高度，因此有：2^(h-1)<n<2^h萨西，總之可以認(rèn)為：h=logn （實(shí)際計算得到應(yīng)該是 log₂n+1 < h <= log₂n ）;
?綜上所述得到：S = n - logn -1
?所以時間復(fù)雜度為：O(n)（堆的初始化過程）有鹿。

三、堆元素的插入

?剛已經(jīng)分析了堆的初始化過程谎脯，那接下來我們來探究下葱跋，怎樣往一個堆里面去插入數(shù)據(jù)。

（一）基本插入過程

?堆的插入操作是自底向上進(jìn)行的【這里指每個結(jié)點(diǎn)是向上進(jìn)行調(diào)整】源梭，每次從堆的最后一個結(jié)點(diǎn)開始插入（將插入的值放入完全二叉樹的最后一個結(jié)點(diǎn)）娱俺，為了維持堆的性質(zhì)，還要從插入結(jié)點(diǎn)開始依次往前遞歸咸产，去維持堆的三個特性矢否。
?取插入結(jié)點(diǎn)的父節(jié)點(diǎn)，比較父節(jié)點(diǎn)的值和插入結(jié)點(diǎn)的值脑溢，將較小的值交換到父節(jié)點(diǎn)位置僵朗。再以父節(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，重復(fù)上一步操作屑彻，直到遇到父節(jié)點(diǎn)比插入結(jié)點(diǎn)值小验庙，就可以結(jié)束遞歸。

（二）實(shí)例分析

?這里僅以大頂堆作為例子講解社牲，用的還是上述得到的大頂堆粪薛，我們來往堆里插入新的元素。

大頂堆

?我們現(xiàn)在有這樣的三個數(shù)46搏恤、70违寿、50等待我們插入湃交，一起來分析下。

插入46：

?得到下圖：

插入46圖片1

?取插入結(jié)點(diǎn)46的父節(jié)點(diǎn)45藤巢，比較父結(jié)點(diǎn)的值和插入結(jié)點(diǎn)的值搞莺，發(fā)現(xiàn)不滿足最大堆的性質(zhì)，因此將較大的值交換到父節(jié)點(diǎn)位置掂咒。得到下圖：

45和46交換

?以父結(jié)點(diǎn)46為當(dāng)前結(jié)點(diǎn)才沧，判斷交換后的結(jié)點(diǎn)是否滿足堆的性質(zhì)。向上找到結(jié)點(diǎn)46的父結(jié)點(diǎn)47绍刮，比較它們的值温圆，發(fā)現(xiàn)滿足最大堆的性質(zhì)，不需要再進(jìn)行調(diào)整孩革，本次插入操作結(jié)束岁歉。
?

插入70

?得到下圖：

插入70

?取插入結(jié)點(diǎn)70的父節(jié)點(diǎn)46，比較父結(jié)點(diǎn)的值和插入結(jié)點(diǎn)的值膝蜈，發(fā)現(xiàn)不滿足最大堆的性質(zhì)刨裆，因此將較大的值交換到父節(jié)點(diǎn)位置。得到下圖：

46和70交換

?以父結(jié)點(diǎn)70為當(dāng)前結(jié)點(diǎn)彬檀，判斷交換后的結(jié)點(diǎn)是否滿足堆的性質(zhì)。向上找到結(jié)點(diǎn)70的父結(jié)點(diǎn)瞬女，發(fā)現(xiàn)不滿足最大堆的性質(zhì)窍帝，需要再進(jìn)行調(diào)整，交換父結(jié)點(diǎn)與子結(jié)點(diǎn)的位置诽偷，得到下圖：

47和70交換

?發(fā)現(xiàn)交換后的結(jié)點(diǎn)70已經(jīng)是根節(jié)點(diǎn)坤学，那么本次插入到此結(jié)束。

插入50：

?得到下圖：

插入50

?取插入結(jié)點(diǎn)50的父節(jié)點(diǎn)18报慕，比較父節(jié)點(diǎn)的值和插入結(jié)點(diǎn)的值深浮，發(fā)現(xiàn)不滿足最大堆的性質(zhì)，將較大的值交換到父節(jié)點(diǎn)位置眠冈。重復(fù)相同的操作飞苇，最終得到下圖：

最終結(jié)果

（三）代碼示例

?根據(jù)上述分析，可得到代碼如下：

//迭代
bool Heap<T>::insert(const T& val)
{
    
    /*
        最大堆特點(diǎn)是根結(jié)點(diǎn)比子節(jié)點(diǎn)都大
        根據(jù)該性質(zhì)進(jìn)行調(diào)整
        (1)索引為i的左孩子的索引是 (2i+1)
       （2）索引為i的右孩子的索引是 (2i+2)
       （3）索引為i的父結(jié)點(diǎn)的索引是 (i-1)/2
    */

    int i=len++;
    while(i>0 && heap[(i-1)/2]<val)
    {
        heap[i]=heap[(i-1)/2];
        i=(i-1)/2;
    }
    heap[i]=val;
    return true;
}

//遞歸
template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
    int i=len++;
    AdjustUps(val,i);
}

template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
    if(i<0)
    {
        return;
    }
    if(heap[(i-1)/2]<val)
    {
        heap[i]=heap[(i-1)/2];
        heap[(i-1)/2]=val;
        i=(i-1)/2;
        AdjustUps(val,i);
    }
}

（四）時間復(fù)雜度分析

?我們可以看到蜗顽，每個結(jié)點(diǎn)的插入都和樹的深度有關(guān)布卡，并且都是不斷的把樹折半來實(shí)現(xiàn)插入，因此是典型的遞歸【當(dāng)然用迭代法也可實(shí)現(xiàn)雇盖，道理一樣】忿等。
?插入一個新的結(jié)點(diǎn)后樹的結(jié)點(diǎn)數(shù)為n，高度為h崔挖，那么此時結(jié)點(diǎn)要交換的最多次數(shù)為：S=h-1
?因?yàn)閔為完全二叉樹的高度贸街，因此有：2^(h-1)<n<2^h庵寞，總之可以認(rèn)為：h=logn （實(shí)際計算得到應(yīng)該是 log₂n+1< h < log₂n ）;
?所以S=O(logn)-1
?插入的時間復(fù)雜度為O(logn)。

四薛匪、堆元素的查找

?堆元素的查找相對還是比較簡單捐川，對于一顆滿二叉樹來說，n個節(jié)點(diǎn)的二叉排序樹的高度為log₂(n+1),其查找效率為O(log₂n)蛋辈，也就是O(logn)属拾，近似于折半查找。
?同樣冷溶，查找可以有迭代和遞歸兩種實(shí)現(xiàn)方法渐白，代碼如下所示：

//非遞歸實(shí)現(xiàn) 
template<typename T>
int Heap<T>::search(const T& val)
{
    int i=0;
    while(i<len)
    {
        if(heap[i]==val)
        {
            return i;
        }
        if(heap[2*i+1]==val)
        {
            return 2*i+1;
        }
        if(heap[2*i+2]==val)
        {
            return 2*i+2; 
        }
        i++;
    }
}

//遞歸實(shí)現(xiàn) 
template<typename T>
int Heap<T>::find(const T& val)
{
    _find(val,0);
}

template<typename T>
int Heap<T>::_find(const T& val,int i)
{
    if(heap[i]==val)
    {
        return i;
    }
    if(heap[2*i+1]==val)
    {
        return 2*i+1;
    }
    if(heap[2*i+2]==val)
    {
        return 2*i+2; 
    }
    _find(val,i++);
    
}

五、堆元素的刪除

?接下來我們來關(guān)注下堆里元素的刪除逞频。我們還是以下圖作為例子來看看怎么進(jìn)行刪除【大頂堆】纯衍。

大頂堆

?我們來刪除結(jié)點(diǎn)50：
?首先找到結(jié)點(diǎn)50對應(yīng)位置的索引,把當(dāng)前堆的最后一個結(jié)點(diǎn)的值賦到當(dāng)前位置，然后刪除最后一個結(jié)點(diǎn)苗胀，堆的當(dāng)前長度減1襟诸。得到下圖：

刪除50

?那么接下來就是對當(dāng)前結(jié)點(diǎn)18進(jìn)行調(diào)整。調(diào)整的方式與上述一致基协。這里只放個圖片：

調(diào)整

?因此對于堆里元素的刪除歌亲，基本過程就是：
?（1）找到待刪除元素的位置索引
?（2）將堆的最后一個元素賦值到該位置上，堆的容量減1
?（3）進(jìn)行堆結(jié)構(gòu)的調(diào)整
?代碼如下所示：

template<typename T>
bool Heap<T>::deletes(const T& val)
{
    int i=search(val);
    heap[i]=heap[len-1];
    len--;
    AdjustDown(heap,i);
    //maxHeapAdjust(heap,i);
}

六澜驮、堆排序

（一）基本思想

?1陷揪、將待排序序列構(gòu)造成一個大頂堆【小頂堆】，此時杂穷，整個序列的最大值【最小值】就是堆頂?shù)母?jié)點(diǎn)悍缠。
?2、將其與末尾元素進(jìn)行交換耐量，此時末尾就為最大值【最小值】飞蚓。
?3、然后將剩余n-1個元素重新構(gòu)造成一個堆廊蜒，這樣會得到n個元素的次小值【次大值】趴拧。如此反復(fù)執(zhí)行，便能得到一個有序序列了山叮。
?注意：降序排序使用大頂堆八堡，升序排序使用小頂堆。

（二）基本步驟

1聘芜、構(gòu)造初始堆

?小編前面已經(jīng)分析了大頂堆與小頂堆的各種有關(guān)操作兄渺。所以這里構(gòu)造初始堆的步驟不再做解釋。堆創(chuàng)建成功之后汰现，接下來就是堆的調(diào)整使最后的數(shù)組有序挂谍。

2叔壤、調(diào)整堆

?這里小編僅以大頂堆作為例子。將堆頂元素與末尾元素進(jìn)行交換口叙，使末尾元素最大炼绘。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換妄田，得到第二大元素俺亮。如此反復(fù)進(jìn)行交換、重建疟呐、交換脚曾。小編用上述得到的大頂堆來進(jìn)行演示，也就是下圖：

大頂堆

?1启具、將堆頂元素47和末尾元素36進(jìn)行交換

47和36交換

?重新調(diào)整結(jié)構(gòu)本讥，使其繼續(xù)滿足堆定義，得到下圖：

調(diào)整

?2鲁冯、再將堆頂元素45與末尾元素18進(jìn)行交換拷沸，得到下圖：

45和18交換

?重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義薯演，得到下圖：

調(diào)整

?3撞芍、再將堆頂元素40與末尾元素36進(jìn)行交換，得到下圖：

40和36交換

?滿足堆結(jié)構(gòu)跨扮，不需調(diào)整繼續(xù)下一步勤庐。

?4、再將堆頂元素36與末尾元素18進(jìn)行交換好港，得到下圖：

36和18交換

?到了這一步，發(fā)現(xiàn)當(dāng)前堆里只剩一個元素米罚，無需調(diào)整钧汹。排序結(jié)束，如下所示：

最終排序

（三）時間復(fù)雜度分析

?調(diào)整堆的復(fù)雜度計算和初始化堆差不多录择，都為O(logn)拔莱。又因?yàn)槎雅判蛎總€結(jié)點(diǎn)都要進(jìn)行一次調(diào)整，因此堆排序的總時間復(fù)雜度為O(nlogn)隘竭。

（四）示例代碼

?小編自己寫了大頂堆的相關(guān)操作代碼塘秦，包括創(chuàng)建，堆化动看、查找尊剔、刪除、排序等等菱皆。小頂堆這里不做分享须误，原理一樣的挨稿。代碼如下所示：

#include <stdio.h>
#include <iostream>
using namespace std;
/*
    本程序中堆的起始索引為0 

*/ 
 
// 堆的實(shí)現(xiàn),二叉樹用數(shù)組來表示
template<typename T>
class Heap
{
public:
    Heap(const int& size);  //創(chuàng)建堆
    ~Heap();
    bool insert(const T& val);  //堆插入非遞歸 
    bool deletes(const T& val);//堆刪除非遞歸 
    void AdjustUp(const T& val);//堆插入調(diào)整 
    void AdjustUps(const T& val,int i);//向上調(diào)整 
    void Delete(const T& val);  //刪除堆中某個數(shù)
    int search(const T& val);   //迭代查找堆中某個數(shù)所在位置
    int find(const T& val); //遞歸查找堆中某個數(shù)所在位置
    int _find(const T& val,int i);  //遞歸查找堆中某個數(shù)所在位置
    void AdjustDown(T* arr, int index) ;//遞歸調(diào)整最大堆 ---向下調(diào)整 
    void maxHeapAdjust(T* arr, int index) ;//迭代調(diào)整最大堆 
    void ArrToHeap(T* arr); //數(shù)組轉(zhuǎn)換為堆
    void AdjustToHeap(T* arr,int arrlength) ;//將數(shù)組元素拷貝到堆中再進(jìn)行調(diào)整，調(diào)整后的heap支持插入刪除等操作 
    void HeapSort();        //大頂堆排序京痢，升序奶甘，最大值放最后位置
    void ArrToHeapToSort(T* arr);       //傳入數(shù)組轉(zhuǎn)換成堆進(jìn)行排序
    void print();               //打印堆元素
    
private:
    T* heap;                    //堆
    int MaxSize,len,temp;           //MaxSize為堆最大容量，Nel為堆目前元素個數(shù),
};


template<typename T>
Heap<T>::Heap(const int& size)
{
    MaxSize = 2*size;
    heap =new T[MaxSize];
    len=size;
}

template<typename T>
Heap<T>::~Heap()
{
    delete []heap;
    heap = NULL;
    MaxSize = 0;
}

/**
    * 遞歸實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)祭椰，使其符合堆的特性臭家。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
template<typename T>
void Heap<T>::AdjustDown(T* arr, int index) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int cMax = li;             // 子節(jié)點(diǎn)值最大索引，默認(rèn)左子節(jié)點(diǎn)方淤。
    int maxIndex = len - 1; //最大索引
    // 左子節(jié)點(diǎn)索引超出計算范圍钉赁，直接返回。
    if (li > maxIndex) 
    {
        return;
    }

    // 先判斷左右子節(jié)點(diǎn)臣淤，哪個較大橄霉。
    if (ri <= maxIndex && arr[li]<arr[ri]) 
    {
        cMax = ri;
    }
    //如果根結(jié)點(diǎn)小于葉子結(jié)點(diǎn)，交換 
    if (arr[index]<arr[cMax]) 
    {
        int item=arr[index];
        arr[index]=arr[cMax];
        arr[cMax]=item;
        AdjustDown(arr, cMax);  // 如果父節(jié)點(diǎn)被子節(jié)點(diǎn)調(diào)換邑蒋，則需要繼續(xù)判斷換下后的父節(jié)點(diǎn)是否符合堆的特性姓蜂。
    }
}

/**
    * 迭代實(shí)現(xiàn) 
    * 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性医吊。
    * @param arr 列表
    * @param index 需要堆化處理的數(shù)據(jù)的索引
    * @param len   未排序的堆（數(shù)組）的長度
*/
template<typename T>
void Heap<T>::maxHeapAdjust(T* arr, int index) 
{
    int li = (index * 2) + 1; // 左子節(jié)點(diǎn)索引
    int ri = li + 1;           // 右子節(jié)點(diǎn)索引
    int item=arr[index];      //存儲該索引結(jié)點(diǎn) 
    int maxIndex = len - 1; //最大索引
    while(li<maxIndex) 
    {
        int cMax = li;             // 子節(jié)點(diǎn)值最大索引钱慢，默認(rèn)左子節(jié)點(diǎn)。
        // 先判斷左右子節(jié)點(diǎn)卿堂，哪個較大束莫。
        if (ri<=maxIndex && arr[li]<arr[ri]) 
        {
            cMax=ri;
        }
        //如果根結(jié)點(diǎn)小于葉子結(jié)點(diǎn)，交換 
        if (item>=arr[cMax]) 
        {
           break;
        }
        arr[li/2]=arr[cMax];//把子節(jié)點(diǎn)值賦值給父結(jié)點(diǎn) 
        li=cMax*2+1;//找到以cMax值為索引的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
        ri=li+1; 
    }
    arr[li/2]=item; //找到正確位置賦值 
}

/*
    將數(shù)組調(diào)整為堆
*/
template<typename T>
void Heap<T>::ArrToHeap(T* arr)
{

    int beginIndex = len/ 2 - 1;  //最后一個非葉子結(jié)點(diǎn)索引 
    /*
        *  將數(shù)組堆化
        *  beginIndex = 第一個非葉子節(jié)點(diǎn)草描。
        *  從第一個非葉子節(jié)點(diǎn)開始即可览绿。無需從最后一個葉子節(jié)點(diǎn)開始。
        *  葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)穗慕，根節(jié)點(diǎn)就是它自己且自己以下值為最大饿敲。
        *  循環(huán)遍歷 
    */
    for (int i = beginIndex; i >= 0; i--) 
    {
       maxHeapAdjust(arr, i);
       // AdjustDown(arr, i);
    }
    
}

/*
    將數(shù)組元素拷貝到heap數(shù)組中再進(jìn)行調(diào)整
    調(diào)整后的heap支持插入刪除等操作 
    
*/

template<typename T>
void Heap<T>:: AdjustToHeap(T* arr,int arrlength)
{
    for(int i=0;i<arrlength;i++)
    {
        heap[i]=arr[i];
    }
    int beginIndex = len/ 2 - 1;  //最后一個非葉子結(jié)點(diǎn)索引 
    /*
        *  將數(shù)組堆化
        *  beginIndex = 第一個非葉子節(jié)點(diǎn)。
        *  從第一個非葉子節(jié)點(diǎn)開始即可逛绵。無需從最后一個葉子節(jié)點(diǎn)開始怀各。
        *  葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)，根節(jié)點(diǎn)就是它自己且自己以下值為最大术浪。
        *  循環(huán)遍歷 
    */
    for (int i = beginIndex; i >= 0; i--) 
    {
       maxHeapAdjust(heap, i);
       // AdjustDown(arr, i);
    }
}

template<typename T>
bool Heap<T>::insert(const T& val)
{
    
    /*
        最大堆特點(diǎn)是根結(jié)點(diǎn)比子節(jié)點(diǎn)都大
        根據(jù)該性質(zhì)進(jìn)行調(diào)整
        (1)索引為i的左孩子的索引是 (2i+1)
       （2）索引為i的右孩子的索引是 (2i+2)
       （3）索引為i的父結(jié)點(diǎn)的索引是 (i-1)/2
    */

    int i=len++;
    while(i>0 && heap[(i-1)/2]<val)
    {
        heap[i]=heap[(i-1)/2];
        i=(i-1)/2;
    }
    heap[i]=val;
    return true;
}

template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
    int i=len++;
    AdjustUps(val,i);
}

template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
    if(i<0)
    {
        return;
    }
    if(heap[(i-1)/2]<val)
    {
        heap[i]=heap[(i-1)/2];
        heap[(i-1)/2]=val;
        i=(i-1)/2;
        AdjustUps(val,i);
    }
}

//非遞歸實(shí)現(xiàn) 
template<typename T>
int Heap<T>::search(const T& val)
{
    int i=0;
    while(i<len)
    {
        if(heap[i]==val)
        {
            return i;
        }
        if(heap[2*i+1]==val)
        {
            return 2*i+1;
        }
        if(heap[2*i+2]==val)
        {
            return 2*i+2; 
        }
        i++;
    }
}

//遞歸實(shí)現(xiàn) 
template<typename T>
int Heap<T>::find(const T& val)
{
    _find(val,0);
}

template<typename T>
int Heap<T>::_find(const T& val,int i)
{
    if(heap[i]==val)
    {
        return i;
    }
    if(heap[2*i+1]==val)
    {
        return 2*i+1;
    }
    if(heap[2*i+2]==val)
    {
        return 2*i+2; 
    }
    _find(val,i++);
    
}



template<typename T>
bool Heap<T>::deletes(const T& val)
{
    int i=search(val);
    heap[i]=heap[len-1];
    len--;
    AdjustDown(heap,i);
    //maxHeapAdjust(heap,i);
}

template<typename T>
void Heap<T>::HeapSort()
{
    int index=len-1;
    int tmplen=len;
    while(index>=0)
    {
        int tmp=heap[index];
        heap[index]=heap[0];
        heap[0]=tmp;
        len--;
        index--;
        AdjustDown(heap,0);
    } 
    len=tmplen;
}

template<typename T>
void Heap<T>::ArrToHeapToSort(T* arr)
{
    ArrToHeap(arr); 
    int index=len-1;
    int tmplen=len;
    while(index>=0)
    {
        int tmp=arr[index];
        arr[index]=arr[0];
        arr[0]=tmp;
        len--;
        index--;
        AdjustDown(arr,0);
    } 
    len=tmplen;//恢復(fù)堆長度 
    for(int i=0;i<len;i++)
    {
        cout<<arr[i]<<" ";
    }
}


template<typename T>
void Heap<T>::print()
{
    for(int i=0;i<len;i++)
    {
        cout<<heap[i]<<"  ";
    }
}


int main()
{
    int arr[5]={18,36,45,40,47};
    int arrlength=sizeof(arr)/sizeof(arr[0]);
    Heap<int> max_heap(arrlength);
    //max_heap.ArrToHeapToSort(arr);
    max_heap.AdjustToHeap(arr,arrlength);
    //max_heap.HeapSort();
    max_heap.AdjustUp(46);
    max_heap.AdjustUp(70);
    max_heap.AdjustUp(50);
    //cout<<max_heap.search(50)<<endl;
    cout<<max_heap.find(50)<<endl;
    //max_heap.insert(46);
    //max_heap.deletes(50);
    max_heap.print();
    return 0;
}

七瓢对、堆應(yīng)用之“優(yōu)先級隊(duì)列”

（一）隊(duì)列與優(yōu)先隊(duì)列的區(qū)別

?1、隊(duì)列是一種FIFO（First-In-First-Out）先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)胰苏，對應(yīng)于生活中的排隊(duì)的場景硕蛹，排在前面的人總是先通過，依次進(jìn)行。
?2妓美、優(yōu)先隊(duì)列是特殊的隊(duì)列僵腺，從“優(yōu)先”一詞，可看出有“插隊(duì)現(xiàn)象”壶栋。比如在火車站排隊(duì)進(jìn)站時辰如，就會有些比較急的人來插隊(duì)，他們就在前面先通過驗(yàn)票贵试。優(yōu)先隊(duì)列至少含有兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert（插入）琉兜，即將元素插入到優(yōu)先隊(duì)列中（入隊(duì)）；以及deleteMin（刪除最小者）毙玻，它的作用是找出豌蟋、刪除優(yōu)先隊(duì)列中的最小的元素（出隊(duì)）。
?3桑滩、優(yōu)先隊(duì)列的實(shí)現(xiàn)常選用二叉堆梧疲，在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊(duì)列一般也是指堆运准。

（二）C++優(yōu)先隊(duì)列簡介

?優(yōu)先隊(duì)列在頭文件#include <queue>中幌氮；其聲明格式為：priority_queue <int> q;【聲明一個名為q的整形的優(yōu)先隊(duì)列】。
?支持的操作:
?q.empty() //如果隊(duì)列為空胁澳，則返回true该互，否則返回false
?q.size() //返回隊(duì)列中元素的個數(shù)
?q.pop() //刪除隊(duì)首元素，但不返回其值
?q.top() //返回具有最高優(yōu)先級的元素值韭畸，但不刪除該元素
?q.push(item) //在基于優(yōu)先級的適當(dāng)位置插入新元素
?有關(guān)操作不做介紹了宇智。

八、一點(diǎn)總結(jié)

?堆的使用場景還是非常豐富的胰丁，掌握堆的各種操作很有必要随橘。啰里啰唆寫了一大堆，或多或少存在些錯誤锦庸，也請指正机蔗，謝謝！

最后編輯于：2021.06.13 10:39:44

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

禁止轉(zhuǎn)載酸员，如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者。

人面猴
序言：七十年代末讳嘱，一起剝皮案震驚了整個濱河市幔嗦，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌沥潭，老刑警劉巖邀泉，帶你破解...
沈念sama閱讀 217,542評論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡汇恤，警方通過查閱死者的電腦和手機(jī)庞钢，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來因谎，“玉大人基括，你說我怎么就攤上這事〔撇恚” “怎么了风皿？”我有些...
開封第一講書人閱讀 163,912評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長匠璧。經(jīng)常有香客問我桐款，道長，這世上最難降的妖魔是什么夷恍？我笑而不...
開封第一講書人閱讀 58,449評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任魔眨，我火速辦了婚禮，結(jié)果婚禮上酿雪，老公的妹妹穿的比我還像新娘驴党。我一直安慰自己，他們只是感情好垫释，可當(dāng)我...
茶點(diǎn)故事閱讀 67,500評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布菇爪。她就那樣靜靜地躺著，像睡著了一般袋励。火紅的嫁衣襯著肌膚如雪侥啤。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,370評論 1贊 302
城市分裂傳說
那天茬故，我揣著相機(jī)與錄音盖灸，去河邊找鬼。笑死磺芭，一個胖子當(dāng)著我的面吹牛赁炎，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播钾腺，決...
沈念sama閱讀 40,193評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼徙垫，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了放棒？” 一聲冷哼從身側(cè)響起姻报，我...
開封第一講書人閱讀 39,074評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎间螟，沒想到半個月后吴旋，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體损肛，經(jīng)...
沈念sama閱讀 45,505評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,722評論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年荣瑟，在試婚紗的時候發(fā)現(xiàn)自己被綠了治拿。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,841評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡笆焰，死狀恐怖劫谅，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情仙辟，我是刑警寧澤同波，帶...
沈念sama閱讀 35,569評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站叠国，受9級特大地震影響未檩，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜粟焊，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,168評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一冤狡、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧项棠，春花似錦悲雳、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評論 0贊 22
一樁弒父案合瓢，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至透典，卻和暖如春晴楔，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背峭咒。一陣腳步聲響...
開封第一講書人閱讀 32,918評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工税弃，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人凑队。一個月前我還...
沈念sama閱讀 47,962評論 2贊 370
代替公主和親
正文我出身青樓则果，卻偏偏與公主長得像，于是被迫代替她去往敵國和親漩氨。傳聞我的和親對象是個殘疾皇子西壮，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,781評論 2贊 354

十大排序算法第二彈：從堆到堆排序

一驱闷、何為“堆”

（一）基本概念

1者娱、滿二叉樹

2朝扼、完全二叉樹

（二）堆的定義及其分類

1弱睦、 定義

2、二叉堆的分類

（三）堆結(jié)點(diǎn)訪問

二锋华、構(gòu)造初始堆（堆調(diào)整）

（一）調(diào)整成大頂堆

第一步

第二步

第三步

示例代碼如下：

（二）調(diào)整成小頂堆

第一步

第二步

第三步

示例代碼

(三)時間復(fù)雜度分析

三、堆元素的插入

（一）基本插入過程

（二）實(shí)例分析

插入46：

插入70

插入50：

（三）代碼示例

（四）時間復(fù)雜度分析

四薛匪、堆元素的查找

五、堆元素的刪除

六澜驮、堆排序

（一）基本思想

（二）基本步驟

1聘芜、構(gòu)造初始堆

2叔壤、調(diào)整堆

（三）時間復(fù)雜度分析

（四）示例代碼

七瓢对、堆應(yīng)用之“優(yōu)先級隊(duì)列”

（一）隊(duì)列與優(yōu)先隊(duì)列的區(qū)別

（二）C++優(yōu)先隊(duì)列簡介

八、一點(diǎn)總結(jié)

推薦閱讀更多精彩內(nèi)容

1弱睦、定義