#include?
#include?
#include?
using?namespace?std;

//隊列的鏈式結構
template
class?linkQueue
{
private:
????struct?node
????{
????????T?data;
????????node*next;
????????node（const?T&xnode*N=NULL）{data=x;next=N;}
????????node（）:next（NULL）{}
????????~node（）{}
????};
????node*f;
public:
????linkQueue（）{?f=NULL;?}
????~linkQueue（）
????{
????????node*t;
????????while（f!=NULL）
????????{?t=f;?f=f->next;?delete?t;?}
????}

????bool?isEmpty（）{?return?f==NULL;?}

????void?enQueue（T?&x）//插入
????{
????????if（?f==NULL?）?f=new?node（x）;
????????else{
????????????node*r=f;
????????????while（r->next!=NULL）?r=r->next;
????????????r->next=new?node（x）;
????????}
????}

????T?deQueue（）//刪除
????{
????????node*t=f;?T?value=f->data;
????????f=f->next;
????????delete?t;
????????return?value;
????}

????T?getHead（）//取隊首元素
????{?T?value=f->data;?return?value;?}
};

//優先級隊列定義
template?
class?priorityQueue
{
public:

????//構造函數-空
????priorityQueue（int?capacity=100）
????????{
????????????array=new?T[capacity];
????????????maxSize=capacity;
????????????currentSize=0;
????????}

????priorityQueue（T?data[]int?size）;
????~priorityQueue（）?{?delete?[]array;?}

????bool?isEmpty（）?{?return?currentSize==0;?}
????void?enQueue（T?&x）;
????T?deQueue（）;
????T?getHead（）?{?return?array[1];?}

????int?findMin（T?x）;
????void?decreaseKey（int?i?T?value）;

????void?show（）
????{
????????cout<????????for（int?j=1;?j<=currentSize;?++j）
????????????cout<????????cout<????}

private:
????int?currentSize;
????T?*array;
????int?maxSize;

????void?doubleSpace（）;
????void?buildHead（）;
????void?percolateDown（int?hole）;
};

//插入
template?
void?priorityQueue::enQueue（T?&?x）
{
????if（currentSize==maxSize-1）?doubleSpace（）;
????//?向上過濾
????int?hole=++currentSize;

????//在x大于空結點的父結點或已過濾到根時終止循環
????for（;?hole>1?&&?x???		array[hole]=array[hole/2];
????array[hole]=x;
}

//刪除
template?
T?priorityQueue::deQueue（）
{
????T?minItem;
????minItem?=?array[1];
????array[1]?=?array[currentSize--];?//將最后一個元素挪到根節點
????percolateDown（1）;?//向下過濾
????return?minItem;
}

template?
void?priorityQueue::percolateDown（int?hole）
{
????int?child;
????T?tmp=array[hole];
????for（;?hole*2<=currentSize;?hole=child）?//每次循環下移一層
????{
????????child=hole*2;?//指向左兒子
????????if（child!=currentSize?&&?array[child+1]????????child++;?//如果右兒子存在且小于左兒子，指向右兒子
????????if（array[child]????????else?break;
??????}
????array[hole]=tmp;
}

//堆構造
template?
void?priorityQueue::buildHead（）
{
????for（int?i=currentSize/2;?i>0;?--i）
????????percolateDown（i）;//調用向下過濾
}

//構造函數-已存在某個數組
template?
priorityQueue::priorityQueue（T?*itemint?size）
????:maxSize（size+10）currentSize（size）
{
???