【C++】模拟实现priority_queue(优先级队列)

     总结一下:

namespace mfc 
{
	template<class T, class Container = vector<T>, class Comapre = less<T>>
    //这里模板的最后一个参数是控制堆模板是排大堆还是小堆的,是一种仿函数
	class priority_queue
	{
	private:
        //成员变量和成员函数子函数
        Container _con;

	public:
		 //成员函数
		
	};
}

    使用一个迭代区间来初始化堆, 其实就是**把这个迭代区间的元素拷贝存入堆中**, **再根据堆的特性将这些元素建成大堆或小堆**即可. 注意, 迭代器的类型有很多种, 我们可以直接将构造函数写成函数模板. 下图是在数据结构堆博客截取的向上建堆的图示过程, 方便大家理解建堆的过程:     

    综上所述,该部分代码如下:

template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		_con.push_back(*first);//按迭代器顺序将数据插入堆中
		++first;
	}

	//建堆   (size-1是下标,再-1是最后一个非叶子结点的公式)
	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(i);//向下调整建堆
	}
}

    因为我们前面实现了迭代区间初始化构造函数,编译器就**不会再给我们生成默认的无参构造函数**,这样会导致我们如果后续使用默认构造时出现一些问题:

    因此我们把无参构造函数补充上,代码如下:

priority_queue()
{}

    priority\_queue的push()就是**在容器尾部插入一个元素**,因为底层的vector或deque都实现有尾插函数push\_back(),所以我们直接调用就可以,但是直接就在尾部插入的话,**会破环堆的结构.导致其不符合大顶堆/小顶堆的特性**,所以我们要**将每个新插入的元素向上调整**到合适的位置才可以,代码如下:

void push(const T& x)
{
	_con.push_back(x);
	AdjustUp(_con.size() - 1);//向上调整函数
}

    因为我们不能保证新入的元素一定完全**符合堆定义的要求**,为了**防止新插入的元素破坏堆的性质**,因此我们**需要对新入堆的元素进行向上调整**,直到调整到其满足堆排序的性质为止.

    为了方便理解,我们拿刚才的大堆做一下演示,**逻辑图示**如下:

    实现代码如下:

void AdjustUp(int child)
{
	Comapre com;//控制大堆还是小堆的仿函数变量

	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (com(_con[parent], _con[child]))//com会根据仿函数的类型来套用相应的仿函数
		{                 
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

    因为priority\_queue的特性使得**堆顶元素一定为当前堆中最大/小的值**,因此我们**出堆操作往往需要出的是堆顶元素**.

    但是我们**不能直接将堆顶元素删除**,因为这样**会导致堆中剩下的元素关系全部乱掉**:

    后面剩余的数据也完全不符合大堆/小堆的特性:

    因此**合理的操作**是**出堆顶就将堆顶元素和堆尾元素交换**,然后**将新堆顶元素向下调整到合适的位置上**:

    代码如下:

void pop()
{
	swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();  //删掉最后一个元素
	AdjustDown(0);    //将堆顶元素(即0号位置元素)向下调整到合适的位置
}

     其次**将交换后的新堆顶元素和两个孩子做比较**,如果是**大堆**,那么**只要孩子比新堆顶元素大**,二者就**交换位置**,如果**两个孩子都比堆顶元素大**,则**堆顶元素和较大的那个孩子交换位置**:

     直到**向下调整到叶子结点位置**或**交换到该堆顶元素比两个孩子结点都大**时**停止向下调整**:

    注意: **向上调整我们只需要将入堆元素与它的双亲结点比较**,而**向下调整时我们需要先比较出结点的两个孩子的大小,然后双亲结点与大的/小的(取决于大堆还是小堆)孩子交换位置**,直到将该结点交换至叶子结点或比两个孩子结点都大/小为止.

    代码如下:

void AdjustDown(int parent)
{
	Comapre com;

	//找左右孩子大的那个
	size_t child = parent * 2 + 1;
			
	while (child < _con.size())
	{
		if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果
		{
			++child;
		}

		if (com(_con[parent], _con[child]))
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

    priority\_queue的top()函数就是**获取堆顶的元素**,vector和deque都有重载operator[]函数,我们可以直接调用它来取到堆顶元素,代码如下:

const T& top()
{
	return _con[0];
}

    priority\_queue的size()函数同样可以直接调用底层容器的size()函数,代码如下:

size_t size()
{
	return _con.size();
}

    priority\_queue的empty()函数同样可以直接调用底层容器的empty()函数,代码如下:

bool empty()
{
	return _con.empty();
}

#include<iostream>
#include<vector>
using namespace std;

#include"PriorityQueue.h"

int main()
{
	mfc::test_priority_queue();

	return 0;
}

namespace mfc 
{
	template<class T, class Container = vector<T>, class Comapre = less<T>>
	class priority_queue
	{
	private:
		void AdjustDown(int parent)
		{
			Comapre com;

			//找左右孩子大的那个
			size_t child = parent * 2 + 1;
			
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果
				{
					++child;
				}

				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustUp(int child)
		{
			Comapre com;

			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

	public:
		 priority_queue()
		 {}

		 template<class InputIterator>
		 priority_queue(InputIterator first, InputIterator last)
		 {
			 while (first != last)
			 {
				 _con.push_back(*first);
				 ++first;
			 }

			 //建堆   (size-1是下标再-1是最后一个非叶子结点的公式)
			 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			 {
				 AdjustDown(i);
			 }

		 }
		 void push(const T& x)
		 {
			 _con.push_back(x);
			 AdjustUp(_con.size() - 1);
		 }
		 void pop()
		 {
			 swap(_con[0], _con[_con.size() - 1]);
			 _con.pop_back();
			 AdjustDown(0);
		 }
		const T& top()
		{
			return _con[0];
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};

	void test_priority_queue()
	{
		priority_queue<int,vector<int>,greater<int>> pq;//传greater是小堆,默认是less大堆
		pq.push(3);
		pq.push(1);
		pq.push(5);
		pq.push(7);
		pq.push(2);
		
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}