C 堆

堆（Heap）

堆，是一種十分基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，也是優(yōu)先隊(duì)列實(shí)現(xiàn)的最好方法掏婶，其本身的實(shí)現(xiàn)也挺簡(jiǎn)單的亏镰。廢話不多說(shuō)，我們直接來(lái)看堆的一些描述和特性套么。

二叉樹(shù)

首先培己，堆其實(shí)就是一顆完全二叉樹(shù)~~(不了解二叉樹(shù)的可以看看這個(gè)《C/C++ 二叉樹(shù)》)~~。

在描述一顆二叉樹(shù)的時(shí)候违诗，我們完全可以使用類似鏈表的方式漱凝，一個(gè)數(shù)據(jù)域來(lái)儲(chǔ)存數(shù)據(jù)，兩個(gè)指針來(lái)指向其左右節(jié)點(diǎn)诸迟。但這樣儲(chǔ)存會(huì)導(dǎo)致空間的浪費(fèi)茸炒，所以可以采用數(shù)組來(lái)儲(chǔ)存二叉樹(shù)。

堆正是一種特殊的二叉樹(shù)阵苇，也就是之前所說(shuō)的完全二叉樹(shù)壁公，這樣子的設(shè)計(jì)，可以保證在數(shù)組中绅项，空間不會(huì)被浪費(fèi)紊册，因此他的儲(chǔ)存效率還是蠻高的。

完全二叉樹(shù)

先來(lái)看一下完全二叉樹(shù)長(zhǎng)啥樣快耿。

完全二叉樹(shù)

可以看出來(lái)囊陡，這棵樹(shù)如果一層層，從左到右標(biāo)上號(hào)掀亥，是連續(xù)的~~(具體的描述可以看這個(gè)《C/C++ 二叉樹(shù)》)~~撞反，這正符合了數(shù)組這種連續(xù)的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，因此非常適合用數(shù)組（本質(zhì)上就是連續(xù)的內(nèi)存空間）來(lái)進(jìn)行實(shí)現(xiàn)搪花。

數(shù)組存儲(chǔ)

講了那么多遏片，我們先用數(shù)組來(lái)存一波二叉樹(shù)吧。

重新標(biāo)號(hào)

還是剛剛那棵樹(shù)撮竿，原汁原味吮便，不過(guò)這回我把標(biāo)號(hào)從1開(kāi)始了，這樣儲(chǔ)存的時(shí)候計(jì)算下標(biāo)會(huì)更方便幢踏。

不難發(fā)現(xiàn)髓需，任何一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的標(biāo)號(hào) $p$ 等于該節(jié)點(diǎn)標(biāo)號(hào) $i$ 除以2，并向下取整房蝉，即 $p = \lfloor{i / 2}\rfloor$ 授账。

同樣的枯跑，一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn) $i1$ ， $i2$ 分別等于該節(jié)點(diǎn) $p$ 的下標(biāo) 乘以2 和乘2加1白热。即 $i1 = p \times 2$ 敛助， $i2 = p \times 2 + 1$ 。

因此屋确，我們?cè)趦?chǔ)存的時(shí)候只要注意下纳击，數(shù)組下標(biāo)從1開(kāi)始計(jì)算。

上面的都是廢話攻臀，正文開(kāi)始焕数。。刨啸。堡赔。

堆的描述

堆，正如他的字面意思设联，是一層層堆上去的善已，每一層之間都有一些特殊的關(guān)系。

在這其中就分為了兩種堆离例，一種叫做大頂堆换团，另一種叫做小頂堆，其區(qū)分的方式便是父節(jié)點(diǎn)和其子節(jié)點(diǎn)之間的關(guān)系不同宫蛆。

小頂堆

字面意思艘包，也就是在最上面的頂點(diǎn)(root節(jié)點(diǎn))是整個(gè)堆最小的，往下走想虎，每一個(gè)上面的節(jié)點(diǎn)都比下面的小。

每個(gè)父節(jié)點(diǎn)都比子節(jié)點(diǎn)小叛拷。

大頂堆

同小頂堆的描述磷醋，也就是在最上面的頂點(diǎn)(root節(jié)點(diǎn))是整個(gè)堆最大的，往下走胡诗，每一個(gè)上面的節(jié)點(diǎn)都比下面的大。

每個(gè)父節(jié)點(diǎn)都比子節(jié)點(diǎn)大淌友。

實(shí)現(xiàn)

根據(jù)堆的描述煌恢，我們很容易就用數(shù)組實(shí)現(xiàn)出來(lái)。

不管怎么說(shuō)我們先開(kāi)一個(gè)數(shù)組：

int a[1000];

然后再開(kāi)一個(gè)變量記錄堆中元素總數(shù)震庭。

int n = 0; // 代表當(dāng)前堆中元素?cái)?shù)量

接著瑰抵，我們很容易寫出一個(gè)插入函數(shù)：

void push(int num)
{
    a[++ n] = num;
}

但這樣也只僅僅是插入元素至數(shù)組，那么我們?cè)趺磥?lái)維護(hù)一個(gè)堆呢器联？

我們這邊以大頂堆作為例子來(lái)進(jìn)行演示二汛。

維護(hù)堆

插入

很容易理解婿崭，如果一個(gè)堆里沒(méi)有元素或者只有一個(gè)元素，那他就是符合堆的描述的肴颊。

那么氓栈，我們?cè)诓迦氲诙€(gè)元素的時(shí)候，就有可能出現(xiàn)子節(jié)點(diǎn)比父節(jié)點(diǎn)大的情況婿着，這時(shí)候我們就需要進(jìn)行交換授瘦。而每個(gè)這樣的上下交換，便叫做shift-up竟宋。

上浮過(guò)程

上圖描繪的便是一個(gè)堆簡(jiǎn)單的維護(hù)過(guò)程提完。在大頂堆中，只要發(fā)現(xiàn)新插入的元素比其父節(jié)點(diǎn)來(lái)得大丘侠，那就進(jìn)行交換徒欣，然后一直重復(fù)這個(gè)操作到root節(jié)點(diǎn)。很明顯蜗字，插入一次的時(shí)間復(fù)雜度是 $O(logn)$ 打肝。

根據(jù)這個(gè)過(guò)程，我們很容易就寫出代碼秽澳。

首先隨便寫一個(gè)交換闯睹，當(dāng)然用C++的algorithm頭文件也行。

void swap(int &a, int &b)
{
    if (a == b) return; // 防止交換相同元素導(dǎo)致都=0
    a ^= b;
    b ^= a;
    a ^= b;
}

然后就是我們的shift-up的代碼：

~~遞歸版本：~~

void _up(int i)
{
    int p = i / 2;
    if (p == 0) return;
    if (a[i] > a[p]) {
        swap(a[i], a[p]);
        _up(p);
    }
}

循環(huán)版本（一般用這個(gè)）：

void up(int i)
{
    int p = i / 2;
    while (p != 0 && a[i] > a[p])
    {
        swap(a[i], a[p]);
        i = p;
        p /= 2;
    }
}

代碼的意思很直白担神，先計(jì)算一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)p楼吃，然后判斷a[i]與a[p]之間的大小關(guān)系，不對(duì)就交換妄讯，然后移動(dòng)到父節(jié)點(diǎn)孩锡，繼續(xù)這個(gè)過(guò)程。

因此堆的push方法就是這樣的了

void push(int num)
{
    a[++ n] = num;
    up(n);
}

刪除

根據(jù)堆的設(shè)計(jì)亥贸，我們一般刪除的節(jié)點(diǎn)就是root節(jié)點(diǎn)躬窜，也就是對(duì)應(yīng)數(shù)組的a[1]。

刪除的方式炕置，其實(shí)也挺簡(jiǎn)單荣挨，交換a[1]和a[n]，也就是交換root節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)朴摊，然后在從上到下進(jìn)行一遍維護(hù)默垄，也就是shift-down操作，恰好和之前的shift-up操作相反甚纲。

下沉操作

圖中口锭，紅色的代表刪除的節(jié)點(diǎn)，橙色的代表位置不正確的節(jié)點(diǎn)介杆，最后一直進(jìn)行shift-down操作鹃操，使所有節(jié)點(diǎn)歸位韭寸，復(fù)雜度為 $O(logn)$ 。

同時(shí)荆隘，最后這個(gè)堆中所有的元素是呈一定的順序的恩伺，將它以普通的數(shù)組展現(xiàn)出來(lái)的時(shí)候，它便是升序排序排好的：[1, 2, 3, 4, 5]臭胜，因此有一種排序就叫做 $堆排序$ 莫其。

同樣的，我還是給出兩個(gè)版本耸三。
~~遞歸版本：~~

void _down(int i)
{
    int k = i * 2;
    if (k > n) return;
    if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    if (a[i] < a[k])
    {
        swap(a[i], a[k]);
        _down(k);
    }
}

循環(huán)版本：

void down(int i)
{
    int k = i * 2;
    if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    while (k <= n && a[i] < a[k])
    {
        swap(a[i], a[k]);
        i = k;
        k *= 2;
        if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    }
}

上述代碼的意思就是首先計(jì)算他的兒子節(jié)點(diǎn)k的下標(biāo)乱陡，然后比較左右兩個(gè)兒子的大小，選擇大的那個(gè)仪壮，之后再與之交換憨颠，然后一直進(jìn)行這個(gè)過(guò)程，直到符合為止积锅。

有了shift-down函數(shù)做基礎(chǔ)爽彤，那么刪除函數(shù)，也就變得十分簡(jiǎn)單缚陷，只要交換頭尾元素即可适篙。

void pop()
{
    if (n > 0) // n是元素個(gè)數(shù)，要注意>0才能pop
    {
        swap(a[1], a[n --]); // 交換頭尾元素
        down(1); // 開(kāi)始shift-down
    }
}

建堆

建堆箫爷，是將一個(gè)不符合堆的描述的數(shù)組轉(zhuǎn)化成一個(gè)符合堆的描述的一個(gè)數(shù)組嚷节。

不要把這個(gè)過(guò)程想得太復(fù)雜，其實(shí)很簡(jiǎn)單虎锚，僅僅只需要用到上文中的shift-down函數(shù)即可硫痰。

一顆完全二叉樹(shù)

還是以上文中的那棵樹(shù)為例，我們假設(shè)需要構(gòu)建一個(gè)大頂堆窜护，而輸入的數(shù)組為：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]（如圖所示）效斑。

那么，我們只需要從 $最后一個(gè)擁有子節(jié)點(diǎn)的父節(jié)點(diǎn)$ 開(kāi)始遞減柱徙，直到root節(jié)點(diǎn)缓屠。

很顯然，圖中最后一個(gè)父節(jié)點(diǎn)便是6號(hào)節(jié)點(diǎn)护侮，所以說(shuō)我們只需for (int i = 6;i >= 1;i --)一直遞減即可敌完。

由上文的規(guī)律可知：

任何一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的標(biāo)號(hào) $p$ 等于該節(jié)點(diǎn)標(biāo)號(hào) $i$ 除以2，并向下取整概行，即 $p = \lfloor{i / 2}\rfloor$ 。

所以弧岳，只要根據(jù)最后一個(gè)節(jié)點(diǎn)的下標(biāo)凳忙，即可求出最后一個(gè)父節(jié)點(diǎn)的下標(biāo)业踏。即 $P = \lfloor{n/2}\rfloor$ 。

建堆代碼：

void heapify()
{
    for (int i = n / 2;i >= 1;i --)
    {
        down(i);
    }
}

值得注意的是涧卵，這種方式的時(shí)間復(fù)雜度是 $O(n)$ 勤家，推倒過(guò)程百度上很多，可以查閱柳恐。

完整代碼

//
//  main.cpp
//  Heap
//
//  Created by JackLee on 2020/2/20.
//  Copyright ? 2020 JackLee. All rights reserved.
//

#include <stdio.h>

//------------------------------------------------------------------------
//------------------------------打印堆函數(shù)BEGIN-----------------------------
#include <math.h>
#include <vector>

using namespace std;

struct ps {
    int dps;
    int length;
    int type;
};

void print_binTree(int *root, int n, int index, int d, int lr, vector<ps> dps) // 打印堆函數(shù)伐脖，用于直觀的顯示堆中元素
{
    if (index > n) return;
    
    ps p = {d, (int) log10(root[index]) + 1, index * 2 + 1 <= n && lr == 0};
    if (dps.size() <= d) dps.push_back(p);
    else dps[d] = p;
    print_binTree(root, n, index * 2 + 1, d + 1, 1, dps);
    for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
    {
        if (i -> type && i -> dps != 0) printf("|");
        else printf(".");
        for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
        {
            printf(".");
        }
    }
    if (d != 0) printf("|-");
    printf("%d",root[index]);
    if (index * 2 <= n || index * 2 + 1 <= n) printf("-|");
    printf("\n");
    dps[d].type = index * 2 <= n && lr;
    print_binTree(root, n, index * 2, d + 1, 0, dps);
}
//------------------------------打印堆函數(shù)END-------------------------------
//------------------------------------------------------------------------


int a[1000]; // 從1開(kāi)始
int n = 0;

void swap(int &a, int &b)
{
    if (a == b) return; // 防止交換相同元素導(dǎo)致都=0
    a ^= b;
    b ^= a;
    a ^= b;
}

void _up(int i)
{
    int p = i / 2;
    if (p == 0) return;
    if (a[i] > a[p]) {
        swap(a[i], a[p]);
        _up(p);
    }
}

void up(int i)
{
    int p = i / 2;
    while (p != 0 && a[i] > a[p])
    {
        swap(a[i], a[p]);
        i = p;
        p /= 2;
    }
}

void _down(int i)
{
    int k = i * 2;
    if (k > n) return;
    if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    if (a[i] < a[k])
    {
        swap(a[i], a[k]);
        _down(k);
    }
}

void down(int i)
{
    int k = i * 2;
    if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    while (k <= n && a[i] < a[k])
    {
        swap(a[i], a[k]);
        i = k;
        k *= 2;
        if (k + 1 <= n && a[k + 1] > a[k]) k ++;
    }
}

void push(int num)
{
    a[++ n] = num;
    up(n);
}

void pop()
{
    if (n > 0)
    {
        swap(a[1], a[n --]);
        down(1);
    }
}

void heapify()
{
    for (int i = n / 2;i >= 1;i --)
    {
        down(i);
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    printf("The heap array's length: ");
    scanf("%d",&t);
    int in;
    for (int i = 1;i <= t;i ++) scanf("%d",a + i);
    n = t;
    heapify();
    printf("Heapified\n");
    print_binTree(a, n, 1, 0, 1, vector<ps>());
    printf("\n");
    while (1)
    {
        printf("Operation? (0 - push, 1 - pop, 2 - sort and quit, else - quit): ");
        scanf("%d",&in);
        if (!in)
        {
            printf("Your number: ");
            scanf("%d",&in);
            push(in);
            print_binTree(a, n, 1, 0, 1, vector<ps>());
            printf("\n");
        } else if (in == 1)
        {
            printf("Poped: %d\n",a[1]);
            pop();
            print_binTree(a, n, 1, 0, 1, vector<ps>());
            printf("\n");
            
        } else if (in == 2)
        {
            t = n;
            printf("The final array: [");
            while (n) pop();
            for (int i = 1;i <= t;i ++)
            {
                if (i != 1) printf(", ");
                printf("%d",a[i]);
            }
            printf("]\n");
            break;
        } else break;
        
    }
    return 0;
}

最后編輯于：2020.02.24 15:21:52

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市乐设，隨后出現(xiàn)的幾起案子讼庇，更是在濱河造成了極大的恐慌，老刑警劉巖近尚，帶你破解...
沈念sama閱讀 217,406評(píng)論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蠕啄，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡戈锻，警方通過(guò)查閱死者的電腦和手機(jī)歼跟，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,732評(píng)論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)格遭，“玉大人哈街，你說(shuō)我怎么就攤上這事【苎福” “怎么了骚秦？”我有些...
開(kāi)封第一講書(shū)人閱讀 163,711評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)坪它。經(jīng)常有香客問(wèn)我骤竹，道長(zhǎng)，這世上最難降的妖魔是什么往毡？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,380評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任蒙揣，我火速辦了婚禮，結(jié)果婚禮上开瞭，老公的妹妹穿的比我還像新娘懒震。我一直安慰自己，他們只是感情好嗤详，可當(dāng)我...
茶點(diǎn)故事閱讀 67,432評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布个扰。她就那樣靜靜地躺著，像睡著了一般葱色。火紅的嫁衣襯著肌膚如雪递宅。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 51,301評(píng)論 1贊 301
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音办龄，去河邊找鬼烘绽。笑死，一個(gè)胖子當(dāng)著我的面吹牛俐填，可吹牛的內(nèi)容都是我干的安接。我是一名探鬼主播，決...
沈念sama閱讀 40,145評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼英融，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼盏檐！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起驶悟，我...
開(kāi)封第一講書(shū)人閱讀 39,008評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤胡野，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后撩银，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體给涕，經(jīng)...
沈念sama閱讀 45,443評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,649評(píng)論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年额获，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了够庙。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,795評(píng)論 1贊 347
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡抄邀，死狀恐怖耘眨，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情境肾，我是刑警寧澤剔难，帶...
沈念sama閱讀 35,501評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站奥喻，受9級(jí)特大地震影響偶宫，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜环鲤，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,119評(píng)論 3贊 328
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一纯趋、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧冷离，春花似錦吵冒、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,731評(píng)論 0贊 22
一樁弒父案痹栖，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至瞭空，卻和暖如春揪阿，著一層夾襖步出監(jiān)牢的瞬間疗我，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,865評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工南捂，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留碍粥，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,899評(píng)論 2贊 370
代替公主和親
正文我出身青樓黑毅，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親钦讳。傳聞我的和親對(duì)象是個(gè)殘疾皇子矿瘦，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,724評(píng)論 2贊 354