十二、二叉堆（Binary Heap）
經(jīng)歷了上一篇實(shí)現(xiàn)AVL樹(shù)的繁瑣，這篇就顯得非常easy了。
首先說(shuō)說(shuō)數(shù)據(jù)結(jié)構(gòu)概念——堆（Heap），其實(shí)也沒(méi)什么大不了，簡(jiǎn)單地說(shuō)就是一種有序隊(duì)列而已，普通的隊(duì)列是先入先出，而二叉堆是：最小先出。
這不是很簡(jiǎn)單么？如果這個(gè)隊(duì)列是用數(shù)組實(shí)現(xiàn)的話(huà)那用打擂臺(tái)的方式從頭到尾找一遍，把最小的拿出來(lái)不就行了？行啊，可是出隊(duì)的操作是很頻繁的，而每次都得打一遍擂臺(tái)，那就低效了，打擂臺(tái)的時(shí)間復(fù)雜度為Ο(n)，那如何不用從頭到尾fetch一遍就出隊(duì)呢？二叉堆能比較好地解決這個(gè)問(wèn)題，不過(guò)之前先介紹一些概念。
完全樹(shù)（Complete Tree）：從下圖中看出，在第n層深度被填滿(mǎn)之前，不會(huì)開(kāi)始填第n+1層深度，還有一定是從左往右填滿(mǎn)。
再來(lái)一棵完全三叉樹(shù)：
這樣有什么好處呢？好處就是能方便地把指針省略掉，用一個(gè)簡(jiǎn)單的數(shù)組來(lái)表示一棵樹(shù)，如圖：
那么下面介紹二叉堆：二叉堆是一種完全二叉樹(shù)，其任意子樹(shù)的左右節(jié)點(diǎn)（如果有的話(huà)）的鍵值一定比根節(jié)點(diǎn)大，上圖其實(shí)就是一個(gè)二叉堆。
你一定發(fā)覺(jué)了，最小的一個(gè)元素就是數(shù)組第一個(gè)元素，那么二叉堆這種有序隊(duì)列如何入隊(duì)呢？看圖：
假設(shè)要在這個(gè)二叉堆里入隊(duì)一個(gè)單元，鍵值為2，那只需在數(shù)組末尾加入這個(gè)元素，然后盡可能把這個(gè)元素往上挪，直到挪不動(dòng)，經(jīng)過(guò)了這種復(fù)雜度為Ο(logn)的操作，二叉堆還是二叉堆。
那如何出隊(duì)呢？也不難，看圖：
出隊(duì)一定是出數(shù)組的第一個(gè)元素，這么來(lái)第一個(gè)元素以前的位置就成了空位，我們需要把這個(gè)空位挪至葉子節(jié)點(diǎn)，然后把數(shù)組最后一個(gè)元素插入這個(gè)空位，把這個(gè)“空位”盡量往上挪。這種操作的復(fù)雜度也是Ο(logn)，比Ο(n)強(qiáng)多了吧？
嘗試自己寫(xiě)寫(xiě)代碼看，當(dāng)然了，我也寫(xiě)（這個(gè)得動(dòng)動(dòng)手啦，比AVL容易多了）：
#include "stdio.h"
#define SWAP_TWO_INT(a, b) \
a^=b; b^=a; a^=b;
class CBinaryHeap
{
public:
CBinaryHeap(int iSize = 100);
~CBinaryHeap();
//Return 0 means failed.
int Enqueue(int iVal);
int Dequeue(int &iVal);
int GetMin(int &iVal);
#ifdef _DEBUG
void PrintQueue();
#endif
protected:
int *m_pData;
int m_iSize;
int m_iAmount;
};
CBinaryHeap::CBinaryHeap(int iSize)
{
m_pData = new int[iSize];
m_iSize = iSize;
m_iAmount = 0;
}
CBinaryHeap::~CBinaryHeap()
{
delete[] m_pData;
}
#ifdef _DEBUG
int CBinaryHeap::Enqueue(int iVal)
{
if(m_iAmount==m_iSize)
return 0;
//Put this value to the end of the array.
m_pData[m_iAmount] = iVal;
++m_iAmount;
int iIndex = m_iAmount - 1;
while(m_pData[iIndex] < m_pData[(iIndex-1)/2])
{
//Swap the two value
SWAP_TWO_INT(m_pData[iIndex], m_pData[(iIndex-1)/2])
iIndex = (iIndex-1)/2;
}
return 1;
}
#endif
int CBinaryHeap::Dequeue(int &iVal)
{
if(m_iAmount==0)
return 0;
iVal = m_pData[0];
int iIndex = 0;
while (iIndex*2<m_iAmount)
{
int iLeft = (iIndex*2+1 < m_iAmount)?(iIndex*2+1):0;
int iRight = (iIndex*2+2 < m_iAmount)?(iIndex*2+2):0;
if(iLeft && iRight) // Both left and right exists.
{
if(m_pData[iLeft]<m_pData[iRight])
{
SWAP_TWO_INT(m_pData[iIndex], m_pData[iLeft])
iIndex = iLeft;
}
else
{
SWAP_TWO_INT(m_pData[iIndex], m_pData[iRight])
iIndex = iRight;
}
}
else if(iLeft) //The iRight must be 0
{
SWAP_TWO_INT(m_pData[iIndex], m_pData[iLeft])
iIndex = iLeft;
break;
}
else
{
break;
}
}
//Move the last element to the blank position.
//Of course, if it is the blank one, forget it.
if(iIndex!=m_iAmount-1)
{
m_pData[iIndex] = m_pData[m_iAmount-1];
//Try to move this element to the top as high as possible.
while(m_pData[iIndex] < m_pData[(iIndex-1)/2])
{
//Swap the two value
SWAP_TWO_INT(m_pData[iIndex], m_pData[(iIndex-1)/2])
iIndex = (iIndex-1)/2;
}
}
--m_iAmount;
return 1;
}
int CBinaryHeap::GetMin(int &iVal)
{
if(m_iAmount==0)
return 0;
iVal = m_pData[0];
return 1;
}
void CBinaryHeap::PrintQueue()
{
int i;
for(i=0; i<m_iAmount; i++)
{
printf("%d ", m_pData[i]);
}
printf("\n");
}
int main(int argc, char* argv[])
{
CBinaryHeap bh;
bh.Enqueue(4);
bh.Enqueue(1);
bh.Enqueue(3);
bh.Enqueue(2);
bh.Enqueue(6);
bh.Enqueue(5);
#ifdef _DEBUG
bh.PrintQueue();
#endif
int iVal;
bh.Dequeue(iVal);
bh.Dequeue(iVal);
#ifdef _DEBUG
bh.PrintQueue();
#endif
return 0;
}