【数据结构】优先级队列的实现

建立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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!