大/小堆:源代码

#pragma once
#include <vector>
#include <assert.h>

//
// 小堆 == 大堆
// 仿函数
//

template<class T>
struct Greater
{
	bool operator() (const T& l, const T& r)
	{
		return l > r;
	}
};

template<class T>
struct Less
{
	bool operator() (const T& l, const T& r)
	{
		return l < r;
	}
};

template<class T, class Compare = Less<T>>
class Heap
{
public:
	Heap()
	{}

	Heap(const T* a, size_t size)
	{
		for(size_t i = 0; i < size; ++i)
		{
			_array.push_back(a[i]);
		}

		// 构建堆
		for (int i = (_array.size()-2)/2; i >=0; --i)
		{
			AdjustDown(i);
		}
	}

	void Push(const T& x)
	{
		_array.push_back(x);
		AdjustUp(_array.size() - 1);

	}

	void Pop()
	{
		assert(_array.size() > 0);
		swap(_array[0], _array[_array.size() - 1]);
		_array.pop_back();
		AdjustDown(0);
	}

	void AdjustDown(int parent)
	{
		int child = parent*2+1;

		while(child < _array.size())
		{
			// 找左右里面小的那一个
			//if (child+1<_array.size()
			//	&& _array[child+1] > _array[child])
			if (child+1 < _array.size()
				&& Compare()(_array[child+1], _array[child]))
			{
				++child;
			}

			// 小的孩子节点跟父节点比较
			//if (_array[child] > _array[parent])
			if(Compare()(_array[child], _array[parent]))
			{
				swap(_array[child], _array[parent]);
				parent = child;
				child = 2*parent+1;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustUp(int child)
	{
		int parent = (child - 1)/2;
		//while (parent >= 0) //?parent不会小于0
		while(child > 0)
		{
			//if (_array[child] > _array[parent])
			if(Compare()(_array[child], _array[parent]))
			{
				swap(_array[child], _array[parent]);
				child = parent;
				parent = (child - 1)/2;
			}
			else
			{
				break;
			}
		}
	}

	int Size()
	{
		return _array.size();
	}

	bool Empty()
	{
		return _array.empty();
	}

	const T& Top()
	{
		return _array[0];
	}

protected:
	vector<T> _array;
	// 函数指针
};

void Test1()
{
	int array[10] = {10, 16, 18, 12, 11, 13, 15, 17, 14, 19};
	Heap<int, Less<int> > hp1(array, 10);
	hp1.Push(5);
	hp1.Pop();

	Heap<int, Greater<int> > hp2(array, 10);
	hp2.Push(100);
	hp2.Pop();
}

template<class T, class Compare = Less<T>>
class PriorityQueue
{
public:
	void Push(const T& x)
	{
		_queue.Push(x);
	}

	void Pop()
	{
		_queue.Pop();
	}

	const T& Top()
	{
		return _queue.Top();
	}

protected:
	Heap<T, Compare> _queue;
};

//template<class T>
//bool Greater(const T& l, const T& r);


// 仿函数
void Test2()
{
	int a1 = 10, a2 = 20;

	Greater<int> GreaterFunc;
	Less<int> LessFunc;

	cout<<GreaterFunc(a1, a2)<<endl;
	cout<<LessFunc(a1, a2)<<endl;

	cout<<Greater<int>()(a1, a2)<<endl;
	cout<<Less<int>()(a1, a2)<<endl;
}