建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
上一章總結(jié)是的堆排序算法，這一章同樣是利用了堆這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)在是優(yōu)先級隊(duì)列。
根據(jù)堆分為最大堆，最小堆，所以優(yōu)先級隊(duì)列也可以分為最大優(yōu)先級隊(duì)列和最小優(yōu)先級隊(duì)列。
優(yōu)先級隊(duì)列的概念和用途書上已經(jīng)寫的很清楚了，我就不再打一遍了。直接寫出具體實(shí)現(xiàn)。
在實(shí)現(xiàn)前先說幾點(diǎn)：
1.上一章說過，堆的length和heapsize要區(qū)分清楚，這一章的優(yōu)先級隊(duì)列里就用到了。
2.優(yōu)先級隊(duì)列用到了上一章的一些函數(shù)比如MaxHeapify()，不記得的可以復(fù)習(xí)下上一章。
以下是代碼及講解(此處實(shí)現(xiàn)的是最大優(yōu)先級隊(duì)列)：
// 堆應(yīng)用之優(yōu)先級隊(duì)列
// Tanky Woo
// Blog: www.WuTianQi.com
#include <iostream>
using namespace std;
const int INF = 999999;
/////////////////////////////////////////////////////////
////////////// 以下代碼在堆排序中已講解過 ///////////////
void MaxHeapify(int *a, int i, int len)
{
int lt = 2*i, rt = 2*i+1;
int largest;
if(lt <= len && a[lt] > a[i])
largest = lt;
else
largest = i;
if(rt <= len && a[rt] > a[largest])
largest = rt;
if(largest != i)
{
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
MaxHeapify(a, largest, len);
}
}
void BuildMaxHeap(int *a, int size)
{
for(int i=size/2; i>=1; --i)
MaxHeapify(a, i, size);
}
void PrintArray(int data[], int size)
{
for (int i=1; i<=size; ++i)
cout <<data[i]<<" ";
cout<< endl << endl;
}
////////////////////////////////////////////////////////////
// 返回具有最大關(guān)鍵字的元素
int HeapMaximum(int *a)
{
return a[1];
}
// 去掉并返回具有最大關(guān)鍵字的元素
// 注意:這里每次MaxHeapify的是heapsize
int HeapExtractMax(int *a, int &heapsize)
{
if(heapsize < 1)
cout << "Heap Underflow" << endl;
int max = a[1];
a[1] = a[heapsize];
--heapsize;
MaxHeapify(a, 1, heapsize);
return max;
}
// 將元素a[i]的值增加到key
void HeapIncreaseKey(int *a, int i, int key)
{
if(key < a[i])
cout << "New key is smaller than current key" << endl;
a[i] = key;
while(i > 1 &&a[i/2] < a[i])
{
int temp = a[i];
a[i] = a[i/2];
a[i/2] = temp;
i /= 2;
}
}
// 插入關(guān)鍵字為key的元素
void MaxHeapInsert(int *a, int key, int &heapsize)
{
++heapsize;
a[heapsize] = -INF;
HeapIncreaseKey(a, heapsize, key);
}
int main()
{
int len, heapsize;
int arr[100] = {0, 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1};
// 區(qū)別len 和 heapsize
// heapsize是堆的大小，而len是初始數(shù)組的總大小。
len = heapsize = 12;
// 首先建堆
BuildMaxHeap(arr, len);
cout << "建堆后: " << endl;
PrintArray(arr, len);
// 使用HeapMaximum
cout << "當(dāng)前最大的元素是: " << endl;
cout << HeapMaximum(arr) << endl << endl;
// 使用HeapExtractMax
cout << "使用HeapExtractMax后: " << endl;
HeapExtractMax(arr,heapsize);
PrintArray(arr, heapsize);
// 再次使用HeapExtractMax
cout << "再次使用HeapExtractMax后: " << endl;
HeapExtractMax(arr,heapsize);
PrintArray(arr, heapsize);
// 使用HeapIncreaseKey
cout << "使用HeapIncreaseKey后: " << endl;
HeapIncreaseKey(arr, 2, 15);
PrintArray(arr, heapsize);
// 使用MaxHeapInsert
cout << "使用MaxHeapInsert后: " << endl;
MaxHeapInsert(arr, 28, heapsize);
PrintArray(arr, heapsize);
}
以下是運(yùn)行結(jié)果：
看上圖的結(jié)果：
在第二次使用HeapExtractMax后，把第二個(gè)數(shù)字即6設(shè)為15，更新后，結(jié)果就是HeapIncreaseKey的輸出。
posted on 2011-04-17 15:00
Tanky Woo 閱讀(1519)
評論(0) 編輯 收藏 引用