优先队列严格说实际上不是一种队列，因为它并不需要遵循队列的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文件以骗过编译器
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/07/19/1246514.html，如需转载请自行联系原作者
