Priority Queue（Heap）的實現及其應用
優先隊列嚴格說實際上不是一種隊列，因為它并不需要遵循隊列的FIFO特性，而要求的基本操作包括：向隊列中插入新的記錄，以及移出隊列中的最大的元素。我們可以以各種不同的方式來實現優先隊列——只要能夠滿足上面的兩個接口就可以了。但是基于堆的優先隊列則具有較好的性能。
優先隊列是一種很有用的數據結構，因為實際上我們不是每時每刻都需要對數據進行嚴格的排序，有時候我們僅僅能夠獲得最大的元素的即可，但是如果以順序查找的方式實現的話，效率上根本滿足不了要求。而堆則提供了一種較高效率的實現策略。
這里給出一個最小堆的實現，并且結合兩個應用進行說明，一個是堆排序，一個是在n個數中尋找第k大的數。
template<typename T>class CPriorityQueue
{//優先隊列類
public: CPriorityQueue(int maxElements=0); CPriorityQueue(T *data,int n); ~CPriorityQueue(void); void Insert(const T& num);//插入優先隊列 T DeleteMin();//返回最小值 bool isEmpty()const;//是否空隊列 bool isFull()const;//是否已經滿了private: int capicity;//容量 int size;//當前大小 T *elements;//元素存儲區 void init(int n);//初始化 void destroy();//銷毀優先隊列
};
#include "stdafx.h"#include <cstdlib>#include "PriorityQueue.h"#include <iostream>using namespace std;template<typename T>void CPriorityQueue<T>::init(int n){//初始化 this->elements = new T[n+1]; this->capicity = n; this->size = 0;}template<typename T>CPriorityQueue<T>::CPriorityQueue(int maxElements){ this->init(maxElements);}template<typename T>CPriorityQueue<T>::CPriorityQueue(T *data,int n){ this->init(n); for(int i=0;i<n;++i)
{
this->Insert(data[i]);
}}template<typename T>void CPriorityQueue<T>::destroy(){//銷毀優先隊列 if(this->elements!=NULL) { delete[] elements; this->elements = NULL; this->size = 0; }}template<typename T>CPriorityQueue<T>::~CPriorityQueue(void){ this->destroy();}template<typename T>bool CPriorityQueue<T>::isEmpty()const{ return this->size==0;}template<typename T>bool CPriorityQueue<T>::isFull() const{ return this->size == this->capicity;}template<typename T>void CPriorityQueue<T>::Insert(const T& num){//入隊列 if(!this->isFull()) { int i; for(i = ++this->size;num<this->elements[i/2];i/=2) this->elements[i] = this->elements [i/2]; this->elements[i] = num; }}template<typename T>T CPriorityQueue<T>::DeleteMin(){ T minElement,lastElement; int i,child; if(!this->isEmpty()) { minElement = this->elements[1];//最小的 lastElement = this->elements[this->size--];//最后一個元素 for(i=1;i*2<=this->size;i=child) { child = i*2; if(child!=this->size&&this->elements[child+1]<this->elements[child]) child++; if(lastElement>this->elements[child]) { this->elements[i] = this->elements[child]; } else break; } this->elements[i] = lastElement; return minElement; } return this->elements[0];//失敗}
// Test.cpp : Defines the entry point for the console application.///***author:phinecos**date:7/19/2008*/#include "stdafx.h"#include "PriorityQueue.cpp"#include <iostream>using namespace std;void printArray(int *data,int n){ int i; for(i=0;i<n;++i) { cout<<data[i]<<" "; } cout<<endl;}void HeapSort(int *data,int n){//堆排序 CPriorityQueue<int> *pQueue = new CPriorityQueue<int>(data,n); int i; for(i=0;i<n;++i) { data[i] = pQueue->DeleteMin(); } delete pQueue;}int FindKthMax(int *data,int n,int k){//在n個數中找第k大的數 CPriorityQueue<int> *pQueue = new CPriorityQueue<int>(data,n); int i,result; for(i=0;i<k;++i) { result = pQueue->DeleteMin(); } delete pQueue; return result;}int main(int argc, char* argv[]){ int a[] = {10,32,55,41,39,12,11,15,20,19,21,22,29,25}; int len = sizeof(a)/sizeof(int); //堆排序演示 cout<<"排序前: "<<endl; printArray(a,len); HeapSort(a,len); cout<<"排序后: "<<endl; printArray(a,len); //尋找第k大數演示 cout<<"請輸入k下標: "<<endl; int k; cin>>k; cout<<"第k大數是: "<<FindKthMax(a,len,k)<<endl; system("pause"); return 0;}注意：VS2008不支持將模板的聲明和實現分開在.h和.cpp中分別實現，總是會報“unresolved external symbol”的錯誤！這是由于模板具體實例化的特殊因素，導致編譯器對分離模式的實現有巨大的復雜度，因而,分離模式至今未能獲得大多數編譯器的支持。所以在目前的編譯環境下，請把模板的聲明與定義全部放在.h文件中!否則，視不同的編譯器，將會有不可預見的編譯及鏈接錯誤生成。但我們可以直接include進來cpp文件以騙過編譯器
全站熱搜
留言列表
