昨天學(xué)習(xí)了用堆排序，今天學(xué)習(xí)了用堆實(shí)現(xiàn)優(yōu)先隊(duì)列。呵呵。都沒(méi)有思路好記錄的，記住堆的性質(zhì)：
1.一個(gè)是他是一個(gè)數(shù)組（當(dāng)然你也可以真的用鏈表來(lái)做。）。
2.他可以看做一個(gè)完全二叉樹(shù)。注意是完全二叉樹(shù)。所以他的葉子個(gè)數(shù)剛好是nSize / 2個(gè)。
3.我使用的下標(biāo)從1開(kāi)始，這樣好算，如果節(jié)點(diǎn)的位置為i,他的父節(jié)點(diǎn)就是i/2,他的左孩子結(jié)點(diǎn)就是i*2,右孩子結(jié)點(diǎn)就是i*2+1，如果下標(biāo)從0開(kāi)始，要復(fù)雜一點(diǎn)。
4.他的父節(jié)點(diǎn)一定不比子節(jié)點(diǎn)?。ㄎ宜傅氖亲畲蠖眩?。
由這些性質(zhì)就可以看出堆得一些優(yōu)點(diǎn)：
1.可以一下找到最大值，就在第一個(gè)位置heap[1].
2.維持堆只需要log(2,n)(n是數(shù)據(jù)個(gè)數(shù))的復(fù)雜度，速度比較快。他只需要比較父與子之間的大小關(guān)系，所以比較次數(shù)就是樹(shù)的高度，而他是一個(gè)完全二叉樹(shù)，所以比較次數(shù)就是log(2,n)。
具體實(shí)現(xiàn)：
具體實(shí)現(xiàn)就看看源代碼吧！努力地組織了一下，呵呵，希望能看懂，奉上源代碼：
#include <stdio.h>
#include <stdlib.h>
//定義一個(gè)堆得結(jié)構(gòu)體，
struct MyHeap
{
int* pnData; //指向數(shù)據(jù)的指針
int nSize; //當(dāng)前堆中的元素個(gè)數(shù)
};
//調(diào)整數(shù)據(jù)，維持堆得性質(zhì)，這個(gè)和上次heapify的作用一樣
//只是這個(gè)時(shí)從子道父節(jié)點(diǎn)這樣的判斷而已。
int IncreaseKey(MyHeap* pHeap, int nPos)
{
//循環(huán)和他父節(jié)點(diǎn)判斷，只要 nPos > 1他就有父節(jié)點(diǎn)
while(nPos > 1)
{
int nMax = pHeap->pnData[nPos];
int nParent = nPos / 2;
//如果他比父節(jié)點(diǎn)大，交換數(shù)據(jù)，并使判斷進(jìn)入父節(jié)點(diǎn)
//（因?yàn)橹挥懈腹?jié)點(diǎn)可能會(huì)影響堆得性質(zhì)。他的數(shù)據(jù)改變了。）
if (nMax > pHeap->pnData[nParent])
{
pHeap->pnData[nPos] = pHeap->pnData[nParent];
pHeap->pnData[nParent] = nMax;
nPos = nParent;
}
else //否則堆沒(méi)有被破壞，退出循環(huán)
{
break;
}
}
return 1;
}
//插入數(shù)據(jù)，這里pnHeap為要插入的隊(duì)，nLen為當(dāng)前堆得大小。
//nData為要插入的數(shù)據(jù)，這里注意報(bào)保證堆得空間足夠。
int Insert(MyHeap* pHeap, int nData)
{
++pHeap->nSize; //添加數(shù)據(jù)到末尾
pHeap->pnData[pHeap->nSize] = nData;
IncreaseKey(pHeap, pHeap->nSize);
return 1;
}
//彈出堆中對(duì)大元素，并使堆得個(gè)數(shù)減一
int PopMaxHeap(MyHeap* pHeap)
{
int nMax = pHeap->pnData[1]; //得到最大元素
//不要忘記維持堆得性質(zhì)，因?yàn)樽畲笤匾呀?jīng)彈出了，主要思路就是
//同他最大孩子填充這里。
int nPos = 1; //起始位1，因?yàn)樗麖棾觯允沁@里開(kāi)始破壞堆得性質(zhì)的
int nChild = nPos * 2; //他的左孩子的位置，
//循環(huán)填充，用最大孩子填充父節(jié)點(diǎn)
while(nChild <= pHeap->nSize)
{
int nTemp = pHeap->pnData[nChild];
if (nChild + 1 <= pHeap->nSize &&
nTemp < pHeap->pnData[nChild + 1])
{
++nChild;
nTemp = pHeap->pnData[nChild];
}
pHeap->pnData[nPos] = nTemp;
nPos = nChild;
nChild *= 2;
}
//最好一個(gè)用最末尾的填充。
pHeap->pnData[nPos] = pHeap->pnData[pHeap->nSize];
--pHeap->nSize; //堆個(gè)數(shù)量減一
return nMax; //返回最大值。
}
//程序入口main
int main()
{
MyHeap myHeap; //定義一個(gè)堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申請(qǐng)數(shù)據(jù)空間
myHeap.nSize = 0; //初始大小為0
for (int i = 1; i <= 10; ++i) //給優(yōu)先隊(duì)列堆里添加數(shù)據(jù)
{
Insert(&myHeap, i);
}
for (int i = 1; i <= 10; ++i) //測(cè)試優(yōu)先隊(duì)列是否建立成功
{
printf("%d ", myHeap.pnData[i]);
}
printf("\n");
while(myHeap.nSize > 0) //逐一彈出隊(duì)列的最大值。并驗(yàn)證
{
printf("%d ", PopMaxHeap(&myHeap));
}
printf("\n");
::free(myHeap.pnData); //最后不要忘記釋放申請(qǐng)的空間
system("pause");
return 0;
}