用C++实现模板优先级队列及堆排序实例

模板优先级队列，数组实现，再熟悉一下常用算法，同时简单的堆排序应用

写了一个是队列自增长，另一个为了演示我还添加了一个叫做FillPq的方法，这个方法可以使用一个数组直接填充到优先级队列里，此时，优先级队列并不优先，然后进行下滤调整，之后建堆完成，输出即可

#include “stdafx.h”

template< class T>
class PriorityQueue
{
private:
T *pq;
int N;
int capacity;
public:
PriorityQueue(void);
~PriorityQueue(void);
void Insert(T x);
T DelTop();
void Swim(int k);
void Sink(int k);
bool Less(int i,int j);
void Swap(int i,int j);
bool Resize();
void FillPq(T arr[],int size);
};

template< class T>
void PriorityQueue<T>::FillPq( T arr[],int size )
{
N=size;
capacity=2*size;
for (int i=0;i<size;i++)
{
pq[i+1]=arr[i];
}
}

template< class T>
PriorityQueue<T>::PriorityQueue(void)
{
pq=new T[10];
N=0;
capacity=10;
}

template< class T>
void PriorityQueue<T>::Insert( T x )
{
if (N==capacity)
{
Resize();
}
pq[++N]=x;
Swim(N);
}

template< class T>
T PriorityQueue<T>::DelTop()
{
T max=pq[1];
Swap(1,N—);
Sink(1);
pq[N+1]=NULL;
return max;
}
//下滤
template< class T>
void PriorityQueue<T>::Sink( int k )
{
while (2k<=N)
{
int j=2k;
if (j<N && Less(j,j+1))
{
j++;
}
if (!Less(k,j))
{
break;
}
Swap(k,j);
k=j;
}
}
//上浮
template< class T>
void PriorityQueue<T>::Swim( int k )
{
while (k>1 && Less(k/2,k))
{
Swap(k,k/2);
}
}

template< class T>
void PriorityQueue<T>::Swap( int i,int j )
{
T temp=pq[i];
pq[i]=pq[j];
pq[j]=temp;
}

template< class T>
bool PriorityQueue<T>::Less( int i,int j )
{
return pq[i]<pq[j];
}

template< class T>
bool PriorityQueue<T>::Resize()
{
T newPq=new T[capacity2];
capacity=capacity*2;
for (int i=1;i<=N;i++)
{
newPq[i]=pq[i];
}
pq=newPq;
return true;
}

template< class T>
PriorityQueue<T>::~PriorityQueue(void)
{
}

然后是堆排序

#include “stdafx.h”

include <iostream>
include <string>
include “PriorityQueue.cpp”

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
PriorityQueue<int> maxPq;

int arr[8]={1,2,4,3,6,8,7,5};
maxPq.FillPq(arr,8);
//建堆
for (int i=4;i&gt;0;i--)
{
maxPq.Sink(i);
}
//输出
for (int i=1;i&lt;=8;i++)
{
cout&lt;&lt;maxPq.DelTop();
}

}