前端之家收集整理的这篇文章主要介绍了
【数据结构】基于堆的优先级队列，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
@H_
301_0@#include <iostream>
#include <assert.h>
#include<stdlib.h>
#include <vector>
using namespace std;
template<typename T>
struct Big
{
bool operator()(const T& l,const T& r)
{
return l>r;
}
};
template<typename T>
struct Less
{
bool operator()(const T& l,const T& r)
{
return l<r;
}
};
template<class T,template<class> class Compare>
class Heap//二叉堆
{
public:
Heap()
{}
void HeapSort(T* a,size_t size)
{
_a.reserve(size);
for(size_t i=0;i<size;i++)
{
_a.push_back(a[i]);
}
for(int i=(_a.size()-2)/2;i>=0;--i)
{
Adjustdown(i);
}
print(_a,size);
}
void Adjustup(size_t child)
{
Compare<T> com;
size_t parent =(child-1)/2;
while(child>0)
{
if(com(_a[child],_a[parent]))
{
swap(_a[parent],_a[child]);
child=parent;
parent=(child-1)/2;
}
else
{
break;
}
}
}
void Adjustdown(size_t parent)
{
size_t child =parent*2+1;
while(child<_a.size())
{
Compare<T> com;
if(child+1<_a.size()&&com(_a[child+1],_a[child]))
{
++child;
}
if(com(_a[child],_a[parent]))
{
swap(_a[parent],_a[child]);
parent=child;
child=parent*2+1;
}
else
{
break;
}
}
}
bool Empty()
{
return _a.size()==0;
}
T& top()
{
assert(!_a.empty());
return _a[0];
}
void Push(const T& x)
{
_a.push_back(x);
size_t _size=_a.size();
Adjustup(_size-1);
print(_a,_size);
}
void Pop()
{
size_t _size=_a.size();
assert(_size>0);
swap(_a[0],_a[_size-1]);
_a.pop_back();
_size=_a.size();
Adjustdown(0);
print(_a,_size);
}
void print(vector<T> a,size_t size)
{
for(int i=0;i<size;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
private:
vector<T> _a;
};
template <class T,template<class> class Compare=Big>
class PriorityQueue//优先级队列
{
public:
void Push(const T& x)
{
hp.Push(x);
}
void Pop()
{
hp.Pop();
}
int Top()
{
return hp.top();
}
protected:
Heap<T,Compare> hp;
};
void test()
{
int Tree[]={23,12,33,45,15,46,17,78,59};
Heap<int,Big> h1;
h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));
}
void test2()
{
int arr[] = { 12,10,43,23,22,67,9 };
Heap<int,Big> h1;
h1.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
Heap<int,Less> h2;
h2.HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
}
void test3()
{
PriorityQueue<int,Big> pq;
pq.Push(1);
pq.Push(23);
pq.Push(33);
pq.Push(46);
pq.Push(15);
pq.Push(43);
pq.Push(27);
pq.Push(81);
pq.Push(19);
pq.Push(10);
pq.Push(11);
cout<<pq.Top()<<endl;
}
