1.什么是二叉堆

二叉堆是一種特殊的堆榜聂，二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）搞疗。二叉堆有兩種：最大堆和最小堆。最大堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值须肆；最小堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值匿乃。

上圖說:

二叉堆

可以看出，這是一顆完全二叉樹,同時(shí)這也是一個(gè)最大堆豌汇。
值得一提的是幢炸，完全二叉樹具有以下性質(zhì)，在之后的分析中會(huì)使用到:
假設(shè)節(jié)點(diǎn)編號(hào)從1開始,編程實(shí)現(xiàn)時(shí)拒贱，數(shù)組從0號(hào)開始阳懂，所以可采用占位符把0號(hào)位置占用，或者將后續(xù)所有節(jié)點(diǎn)全部減一。

• 結(jié)點(diǎn)i的父結(jié)點(diǎn)為結(jié)點(diǎn)i/2 （注意這里是地板除法岩调，舉個(gè)栗子巷燥，在C/JAVA...語言中 直接另1/2等于0，而不是0.5号枕。具體可以這樣寫floor(1/2)也就是將1/2的結(jié)果在向下取整缰揪。）
• 結(jié)點(diǎn)i的子結(jié)點(diǎn)分別為(2*i)和(2*i+1)

同時(shí)，基于完全二叉樹的特性葱淳，二叉堆通常使用數(shù)組來編寫钝腺。

2.二叉堆的基本操作

二叉堆的基本操作為插入，提取最大（最性薏蕖）值艳狐。下面以最大堆作為例子來介紹，最小堆只是最大堆的鏡像反轉(zhuǎn)皿桑，所以我就不多說啦毫目。

2.1插入

insert.gif

在上面的二叉堆中，我們插入了55這個(gè)節(jié)點(diǎn)诲侮。
我們來分析下镀虐，它是如何插入到這個(gè)二叉堆中的：

• 首先按照完全二叉樹的順序，我們?cè)?strong>編號(hào)12這個(gè)地方生成55這個(gè)節(jié)點(diǎn)
• 接著沟绪，由于這是一個(gè)最大二叉堆刮便，所以要比較它的父節(jié)點(diǎn)（如果有的話）和它的大小，這里55是大于7的绽慈，所以兩個(gè)交換了位置
• 循環(huán)第2步恨旱，直到它的父親節(jié)點(diǎn)不比它大，或者已經(jīng)達(dá)到根節(jié)點(diǎn)坝疼。

從上面三步分析中窖杀，我們可以直到發(fā)生，一個(gè)插入的操作無非就是：插入到最后這個(gè)位置裙士，向上更新兩步入客。所以我們可以寫出下面的代碼:

void insert(int e) {
        ensureSize();            //保證空間還足夠插入
        elem[length] = e;        //插入
        heapUp();                //向上更新
        length++;
    }

So,how to headUp()?

  void heapUp() {
        int i = length;
        while (hasParentIndex(i) && elem[parentIndex(i)] < elem[i]) {
            swap(elem[parentIndex(i)], elem[i]);
            i = parentIndex(i);
        }
    }

我相信已經(jīng)足夠簡(jiǎn)單了。一直向上檢查是否有比自己小的元素腿椎，只要有桌硫，就交換。

知道怎么插入節(jié)點(diǎn)了啃炸，那么我們能夠運(yùn)用它來做什么呢铆隘？（廢話，當(dāng)然是插入操作了）南用，其實(shí)最簡(jiǎn)單的我們可以用它來生成二叉堆膀钠。
為了加深印象掏湾，我再貼一張，生成二叉堆動(dòng)態(tài)的圖:

create.gif

生成二叉堆

就隨機(jī)插入一些元素吧肿嘲，randNumber是我寫的隨機(jī)函數(shù)融击，各位同學(xué)看自己熟悉的語言怎么實(shí)現(xiàn)方便就怎么實(shí)現(xiàn)吧。

    for (int i = 0; i < 10; i++) {
        heap.insert(randNumber(0, 1000));
    }

2.2 提取最大（最婿摺）值

最大（最凶鹄恕）堆的根節(jié)點(diǎn)，代表了這個(gè)堆中的最大（最蟹饩取）值拇涤，將它進(jìn)行彈出，在把整棵樹最后的節(jié)點(diǎn)放置到根節(jié)點(diǎn)誉结，再把它交換到恰當(dāng)?shù)奈恢枚焓浚@就是提取操作。

表達(dá)的不是很好惩坑，所以還是貼圖吧

extract.gif

相信你已經(jīng)能夠理解什么是提取操作了掉盅。其實(shí)具體就分為三步：

1. Pop堆頂元素
2. 把當(dāng)前樹（數(shù)組）中最后一個(gè)非空元素提取上來
3. heapDown，更新旭贬，只要遇到比自己大的元素就交換。

那么下面看代碼:

 bool pop() {
        if (!isEmpty()) {
            elem[0] = elem[length - 1];
            length--;
            //swap down
            heapDown();
            return true;
        } else {
            return false;
        }
    }
  
   void heapDown() {
        int i = 0;
        while (hasLeftChild(i)) {
            //find the minimum index of this node's child
            int largerIndex = leftSonIndex(i);
            if (hasRightChild(i) && elem[rightSonIndex(i)] > elem[leftSonIndex(i)]) {
                largerIndex = rightSonIndex(i);
            }
            if (elem[i] > elem[largerIndex]) {
                break;
            }
            swap(elem[i], elem[largerIndex]);
            i = largerIndex;
        }
    }

heapDown操作比heapUp略微復(fù)雜一點(diǎn)搪泳，因?yàn)閺纳贤聲r(shí)有左子樹和右子樹稀轨，我們要檢查哪個(gè)子樹更大,總是把更大的哪個(gè)往上堆，至于為什么岸军，因?yàn)樵酵略叫÷铩?/p>

那么提取操作能做什么呢奋刽？沒錯(cuò)，就是今天的應(yīng)用-堆排序

3.二叉堆應(yīng)用-堆排序

所謂的堆排序艰赞，也就是利用了二叉堆本身性質(zhì)佣谐，在循環(huán)調(diào)用提取操作的一種排序方式，其平均時(shí)間復(fù)雜度為O(nlogn)方妖，是一種排序效率很高的排序方法狭魂。
還是老規(guī)矩，先上圖：

heap_sort.gif

寫個(gè)driver來測(cè)試一下：

int main(void) {
    Heap heap(1000);
    //初始化隨機(jī)種子
    srand((unsigned int) time(NULL));
    for (int i = 0; i < 100000; i++) {
        heap.insert(randNumber(0, 1000000));
    }
    while (!heap.isEmpty()) {
        cout << heap.top() << " ";
        heap.pop();
    }
    return 0;
}

本文中所有的源碼都可以在我的Github上找到：https://github.com/zzbb1199/DataStructure

除了本文党觅，也推薦去看下這個(gè)視頻（需要去外面看看才行喲）,10分鐘搞定堆雌澄，雖然是全英文的，但是講得簡(jiǎn)短而且很清晰杯瞻，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的同時(shí)也鍛煉了自己的英語能力嘛:https://www.youtube.com/watch?v=t0Cq6tVNRBA&t=490s