模板优先级队列及堆排序(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 (2*k<=N)
	{
		int j=2*k;
		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[capacity*2];
	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>0;i--)
	{
	maxPq.Sink(i);
	}
	//输出
	for (int i=1;i<=8;i++)
	{
	cout<<maxPq.DelTop();
	}
}