优先级队列-创新互联

优先级队列首先是一个队列，但是它强调的是“优先”，所以优先级队列又分为大优先队列和最小优先队列。

创新互联为企业级客户提高一站式互联网+设计服务，主要包括成都网站制作、网站建设、成都APP应用开发、微信小程序、宣传片制作、LOGO设计等，帮助客户快速提升营销能力和企业形象，创新互联各部门都有经验丰富的经验，可以确保每一个作品的质量和创作周期，同时每年都有很多新员工加入，为我们带来大量新的创意。 

•  大优先级队列：每次从队列中取出优先级大的数据，删除数据也是删除优先级大的数据。

•  最小优先级队列：每次从队列中取出优先级最小的数据，删除也是删除优先级最小的数据。

 所以我们用一个类去实现优先级队列时就需要用到小顶堆和大顶堆的概念。我们并不关心除了最高优先级和最低优先级的数据在队列中是怎体存储的。

 为了提高代码的复用性，大优先级对列和最小优先级队列都使用同一个堆调整函数，我们可以定义一个比较模板（Compare）也可以说是一个类，不过它是通过重载（）实现的。

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

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

 通过Less和Grearter模板，我们就可以在优先级队列初始化的时候通过传Less或者Greater的对象，来调整是大优先级队列还是最小优先级队列。

  我们的优先级队列所拥有的功能和STL源码的功能差不多。在这我是用一个顺序表来实现队列。以下是具体的实现

#pragma once
#include
#include
using namespace std;

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

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


template class Compare=Less>
class PQueue
{
public:
	PQueue()
		:_size(0)
	{}
	PQueue(const T* a, size_t size)
		:_size(size)
	{
		_data.resize(size);
		for (size_t i = 0; i < size; i++)
		{
			_data[i] = a[i];
		}
		for (int i = (size - 2) / 2; i >= 0; --i)
		{
			_AdjustDown(i);
		}
	}
	size_t Size()
	{
		return _size;
	}
	void Push(const T& d)
	{
		_data.push_back(d);
		++_size;
		_AdjustUp();
	}
	void Pop()
	{
		swap(_data[0], _data[_size - 1]);
		_data.pop_back();
		_AdjustDown(0);
	}
	T& Front()
	{
		return _data[0];
	}
	bool Empty()
	{
		return _size;
	}
protected:
	void _AdjustDown(int parent)
	{
		Compare con;
		int child = parent * 2 + 1;
		while (child < _size)
		{
			if (child + 1 < _size&&con(_data[child + 1], _data[child]))
				++child;
			if (con(_data[child], _data[parent]))
			{
				swap(_data[child], _data[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	void _AdjustUp(int child)
	{
		Compare con;
		parent = (child - 1) / 2;
		while (child > 0)
		{
			if (con(_data[child], _data[parent]))
			{
				swap(_data[child], _data[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}
protected:
	vector _data;
	size_t _size;
};

 优先级队列的核心就是调整大顶堆和小顶堆，如果对于大顶堆和小顶堆有不懂得话可以查看我的博客，互相交流学习。http://helloleex.blog.51cto.com/10728491/1768758

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网页标题：优先级队列-创新互联
文章分享：http://shouzuofang.com/article/djgdso.html