本文共 2244 字，大约阅读时间需要 7 分钟。

【适配器模式】由于建立大堆和建立小堆方式相同，代码相似，所以可以通过添加一个比较器（利用Compare,定义伪函数Less和Greater）实现大小数据的比较，防止大量代码重复。

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

优先级队列的实现利用堆实现

template
   
    
     class 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;}
   

本文出自 “” 博客，请务必保留此出处

转载地址：http://oilbi.baihongyu.com/