【适配器模式】实现优先级队列
【适配器模式】由于建立大堆和建立小堆方式相同,代码相似,所以可以通过添加一个比较器(利用Compare,定义伪函数Less和Greater)实现大小数据的比较,防止大量代码重复。
成都创新互联专注于企业营销型网站、网站重做改版、朔州网站定制设计、自适应品牌网站建设、H5高端网站建设、购物商城网站建设、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为朔州等各大城市提供网站开发制作服务。
templatestruct 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; } }; template class Compare> class Heap { public: Heap(); Heap(const T* a, size_t size); protected: void _AdjustDown(size_t Parent);//下调--建堆 public: vector _a; }; template class Compare> Heap ::Heap() :_a(NULL) {} template class 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); } //建小堆,类似建大堆的方式,从下向上进行调整堆,使该结点处的左右子树都满足小堆 //在进行调小堆时,也通过下调实现 } //下调--建大堆/小堆 template class 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 }; PriorityQueuehp;//大数优先级高 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; }
文章标题:【适配器模式】实现优先级队列
当前路径:http://pwwzsj.com/article/peosis.html