模板优先级队列及堆排序(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&gt;0;i--)
{
maxPq.Sink(i);
}
//输出
for (int i=1;i&lt;=8;i++)
{
cout&lt;&lt;maxPq.DelTop();
}

}

 

comments powered by Disqus