【适配器模式】由于建立大堆和建立小堆方式相同，代码相似，所以可以通过添加一个比较器（利用Compare,定义伪函数Less和Greater）实现大小数据的比较，防止大量代码重复。
创新互联2013年开创至今，先为宁阳等服务建站，宁阳等地企业，进行企业商务咨询服务。为宁阳企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
template
struct Less//小堆调用
{
bool operator()(const T& L, const T& R)
{
return L < R;
}
};
template
struct Greater//大堆调用
{
bool operator()(const T& L, const T& R)
{
return L > R;
}
};
templateclass Compare>
class Heap
{
public:
Heap();
Heap(const T* a, size_t size);
protected:
void _AdjustDown(size_t Parent);//下调--建堆
public:
vector _a;
};
templateclass Compare>
Heap::Heap()
:_a(NULL)
{}
templateclass Compare>
Heap::Heap(const T* a, size_t size)
{
assert(a);
_a.reserve(size);//初始化_a(vector模板的使用)
for (size_t i = 0; i < size; ++i)
{
_a.push_back(a[i]);
}
//建大堆时，从下往上依次判断并调整堆，使该结点的左右子树都满足大堆
for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定义为size_t（无符号）
{
_AdjustDown(i);
}
//建小堆，类似建大堆的方式，从下向上进行调整堆，使该结点处的左右子树都满足小堆
//在进行调小堆时，也通过下调实现
}
//下调--建大堆/小堆
templateclass Compare>
void Heap::_AdjustDown(size_t Parent)
{
Compare com;
size_t Child = Parent * 2 + 1;
while (Child < _a.size())
{//先进行左右结点的比较,使Child为较大的数的下标，然后与父亲结点进行比较，使较大的数据为父亲结点
if (Child + 1 < _a.size() && _a[Child] < _a[Child + 1])//存在右结点再进行比较
{
++Child;
}
if (com(_a[Child], _a[Parent]))//如果用Greater时，为真，则表示子结点大于父亲结点，进行交换
{
swap(_a[Child], _a[Parent]);
Parent = Child;
Child = Parent * 2 + 1;
}
else
{
break;
}
}
}
优先级队列的实现利用堆实现
templateclass Compare>
class PriorityQueue//优先级队列---调用堆实现
{
public:
void Push(const T& x)
{
_hp.Push(x);
}
void Pop()
{
_hp.Pop();
}
bool Empty()
{
return _hp.Empty() == 0;
}
T& Front()
{
return _hp.GetTop();
}
T& Tail()
{
size_t size = _hp.Size();
return _hp._a[size - 1];//将_a设置为public就可以访问
}
size_t Size()
{
return _hp.Size();
}
void PrintPriority()
{
_hp.PrintHeap();
}
private:
Heap _hp;
};
测试用例如下：
void Test()
{//利用适配器模式实现优先级队列
int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
PriorityQueue hp;//大数优先级高
hp.Push(10);
hp.Push(16);
hp.Push(18);
hp.Push(12);
hp.Push(11);
hp.Push(13);
hp.Push(15);
hp.Push(17);
hp.Push(14);
hp.Push(19);
hp.PrintPriority();
cout << "empty: " << hp.Empty() << endl;
cout << "size: " << hp.Size() << endl;
cout << "front: " << hp.Front() << endl;
cout << "tail: " << hp.Tail() << endl;
}创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
文章名称：【适配器模式】实现优先级队列-创新互联
分享路径：
http://cdxtjz.cn/article/cdgjci.html
