【適配器模式】實現優先級隊列

【適配器模式】由于建立大堆和建立小堆方式相同，代碼相似，所以可以通過添加一個比較器（利用Compare,定義偽函數Less和Greater）實現大小數據的比較，防止大量代碼重復。

template<class T>
struct Less//小堆調用
{
	bool operator()(const T& L, const T& R)
	{
		return L < R;
	}
};
template<class T>
struct Greater//大堆調用
{
	bool operator()(const T& L, const T& R)
	{
		return L > R;
	}
};

template<class T, template<class>class Compare>
class Heap
{
public:
	Heap();
	Heap(const T* a, size_t size);
protected:
	void _AdjustDown(size_t Parent);//下調--建堆
public:
	vector<T> _a;
};

template<class T, template<class>class Compare>
Heap<T, Compare>::Heap()
:_a(NULL)
{}
template<class T, template<class>class Compare>
Heap<T, Compare>::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 T, template<class>class Compare>
void Heap<T, Compare>::_AdjustDown(size_t Parent)
{
	Compare<T> 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 T,template<class>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<T, Compare> _hp;
};

測試用例如下：

void Test()
{//利用適配器模式實現優先級隊列
	int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	PriorityQueue<int, Greater> 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;
}