建立PriorityQueue.hpp：

#define_CRT_SECURE_NO_WARNINGS1
#include<iostream>
usingnamespacestd;
#include<assert.h>
#include<vector>
 
 
template<classT>
structLess
{
booloperator()(constT&l,constT&r)
{
returnl<r;
}
};
 
template<classT>
structGreater
{
booloperator()(constT&l,constT&r)
{
returnl>r;
}
};
 
 
template<classT,template<class>classCompare=Less>
classHeap
{
public:
Heap()
:_a(NULL)
{}
 
 
Heap(constT*a,size_tsize)
{
for(inti=0;i<size;i++)
{
_a.push_back(a[i]);
}
for(inti=(size-2)/2;i>=0;i--)
{
_adjustDown(i);
}
}
 
 
void_adjustDown(size_tparent)
{
Compare<T>com;
size_tchild=2*parent+1;
size_tsize=_a.size();
while(child<size)
{
if(child+1<size&&com(_a[child+1],_a[child]))
{
++child;
}
if(com(_a[child],_a[parent]))
{
swap(_a[child],_a[parent]);
parent=child;
child=2*parent+1;
}
else
{
break;
}
}
}
 
 
voidPush(constT&x)
{
_a.push_back(x);
_adjustUp(_a.size()-1);
}
 
 
void_adjustUp(size_tchild)
{
intparent=(child-1)/2;
Compare<T>com;
while(child>0)
{
if(com(_a[child],_a[parent]))
{
swap(_a[parent],_a[child]);
child=parent;
parent=(child-1)/2;
}
else
{
break;
}
}
}
 
 
size_tSize()
{
size_tsize=_a.size();
returnsize;
}
 
 
boolEmpty()
{
assert(Size()>=0);
returnSize()==0;
}
 
 
voidPop()
{
assert(_a.Size()>0);
swap(_a[0],_a[Size-1]);
_a.pop_back();
_adjustDown(0);
}
 
 
T&GetTop()
{
return_a[0];
}
 
 
voidPrint()
{
cout<<"大堆序列："<<endl;
for(inti=0;i<_a.size();i++)
{
cout<<_a[i]<<"";
}
cout<<endl;
}
public:
vector<T>_a;
};
 
 
template<classT,template<class>classCompare=Less>
classPriorityQueue
{
public:
voidPush(constT&x)
{
_hp.Push(x);
}
 
 
voidPop()
{
_hp.Pop();
}
 
 
size_tSize()
{
return_hp.Size();
}
 
 
boolEmpty()
{
_hp.Empty();
}
 
 
T&Top()
{
return_hp.GetTop();
}
 
 
voidPrint()
{
_hp.Print();
}
private:
Heap<T,Compare>_hp;
};

建立PriorityQueue.cpp文件：

#define_CRT_SECURE_NO_WARNINGS1
#pragmaonce
#include"PriorityQueue.hpp"
 
voidTest()
{
inta[]={10,11,13,12,16,18,15,17,14,19};
PriorityQueue<int,Greater>pq;
pq.Push(10);
pq.Push(11);
pq.Push(13);
pq.Push(12);
pq.Push(16);
pq.Push(18);
pq.Push(15);
pq.Push(17);
pq.Push(14);
pq.Push(19);
 
pq.Print();
}
 
 
intmain()
{
Test();
system("pause");
return0;
}