大/小堆:源代码

#pragma once
#include 
#include 

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

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

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

template>
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 _array;
	// 函数指针
};

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

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

template>
class PriorityQueue
{
public:
	void Push(const T& x)
	{
		_queue.Push(x);
	}

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

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

protected:
	Heap _queue;
};

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


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

	Greater GreaterFunc;
	Less LessFunc;

	cout<()(a1, a2)<()(a1, a2)<
以上
10年专注成都网站制作，成都定制网页设计，个人网站制作服务，为大家分享网站制作知识、方案，网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于成都定制网页设计,高端网页制作,对凿毛机等多个方面，拥有多年的营销推广经验。
            
            
                        

            当前标题：大/小堆:源代码            

            标题路径：http://bjjierui.cn/article/jccccs.html