C++ ------>std :: priority_queue-摩杜云开发者社区

各位好友，本期 开战 ------------------>Priority_queue 模拟实现 <------------------------

--------->Priority_queue（优先级队列）介绍：>

（1）. 优先级队列是一种容器适配器，其中第一个元素总是它所包含元素里的最大值；

（2）. 优先级队列存储数据的行为，类似于 堆 ，而优先级队列顶部的元素就是最大的堆顶元素；

（3）. 优先级队列作为一种容器适配器，可将特定容器类封装作为它本身的底层容器类，Vector 与List相比较

------->Vector 进行尾部插入 ~~ 删除数据，更加高效！因此，选择 Vector 作为其底层容器类最合适

------->注意：>元素从特定容器的 “尾部” 弹出，称其为优先级队列的顶部！

（4）. 默认情况下，没有对特定的 Priority_queue（优先级队列）类实例化指定容器，则使用 Vector ！

---------->头文件 “Priority_queue.h”

//priority__模拟实现

#include <iostream>
#include <vector>
#include <algorithm>

using std :: cout;
using std :: endl;
using std :: vector;
using std :: swap;
    
namespace UC
{
  template<class T, class Container = vector<T>>
	class priority_queue
  {
    private:
    
    //向下调整
    void AdjustDown(int parent)
    {
      int child = parent * 2 + 1;
      while(child < _con.size())
      {
       if(child + 1 < _con.size() && _con[child] < _con[child + 1])
        {
         	++child;
        }
        else if(_con[parent] < _con[child])
        {
          swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
         	break;
      }
    }
    //向上调整
    void AdJustUp(int child)
    {
    	int parent = (child -1) / 2;
      while(child > 0)
      {
      	if(_con[parent] < _con[child])
        {
        	swap(_con[child], _con[parent]);
          
          child = partent;
          
          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;
      }
      for(size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
      {
      	AdjustDown(i);
      }
    }
    void pop()
    {
    	swap(_con[0], _con[_con.size() - 1]);
      
      _con.pop_back();
      
      AdjustDowan(0);
    }
    void push(const T& x)
    {
    	_con.push_back(x);
      
      AdjustUp(_con.size() - 1);
    }
    const T& Top()
    {
    	return _con[0];
    }
    bool empty()
    {
			return _con.empty();    
    }
    size_t size() const
    {
    	return _con.size();
    }
    private:
    
    Container _con;
  };
}

----------->“Test.cpp”

//测试 ---->优先级队列
//默认 建大堆
#include "PriorityQueue.h"

int main()
{
  UC :: priority_queue<int> T;
  
  T.push(12);
  T.push(13);
  T.push(16);
  T.push(17);
  
  T.push(21);
  T.push(23);
  
  while(!T.empty())
  {
  	cout << T.Top() << " ";
    
    T.pop();
  }
  
  cout <<endl;
	return 0;
}

为了方便好友们，有更好的观感体验，现附上 彩色 代码图样：>

-------------->"PriorityQueue.h"

C++ ------>std :: priority_queue_Date 类排序__指针访问_玩法

----------->“Test.cpp”

C++ ------>std :: priority_queue_Date 类排序__指针访问_玩法_02

-------------->"PriorityQueue.h" ------->升级版

-------->仿函数与自定义类型 : >

//头文件 “PriorityQueue.h ”
//仿函数 与自定义类__运用
//priority_queue__模拟实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using std :: cout;
using std :: endl;
using std :: vector;
using std :: swap;

//仿函数
template<class T>
  struct Less
  {
  	bool operator()(const T& x, const T& y)
    {
    	return x < y;
    }
  };

template<class T>
  struct Greater
  {
  	bool operator()(const T& x, const T& y)
    {
    	return x > y;
    }
  };
    
namespace UC
{
  template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
  {
    private:
    
    //向下调整
    void AdjustDown(int parent)
    {
      Compare com;
      int child = parent * 2 + 1;
      while(child < _con.size())
      {
       if(child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
        {
         	++child;
        }
        else if(com(_con[parent], _con[child]))
        {
          swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
         	break;
      }
    }
    
    //向上调整
    void AdJustUp(int child)
    {
      Compare com;
      
    	int parent = (child -1) / 2;
      while(child > 0)
      {
      	if(com(_con[parent] , _con[child]))
        {
        	swap(_con[child], _con[parent]);
          
          child = partent;
          
          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;
      }
      for(size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
      {
      	AdjustDown(i);
      }
    }
    void pop()
    {
    	swap(_con[0], _con[_con.size() - 1]);
      
      _con.pop_back();
      
      AdjustDown(0);
    }
    void push(const T& x)
    {
    	_con.push_back(x);
      
      AdjustUp(_con.size() - 1);
    }
    const T& Top()
    {
    	return _con[0];
    }
    bool empty()
    {
			return _con.empty();    
    }
    size_t size() const
    {
    	return _con.size();
    }
    private:
    
    Container _con;
  };
  
  //自定义类型 Date
  class Date
  {
    public:
  	Date(int year = 2018, int month = 06, int day = 07)
      :_year(year)
        ,_month(month)
        ,_day(day)
    {}
    
    bool operator<(const Date& d) const
    {
    	return (_year < d.year) ||
        		(_year == d.year && _month < d.month) ||
      			(_year == d.year && _month == d.month && _day < d.day);
    }
    bool operator>(const Date& d) const
    {
    	return (_year > d._year) ||
        (_year == d.year && _month > d.month) ||
        (_year == d.year && _month == d.month && _day > d.day);
    }
    
    private:
    
    int _year;
    int _month;
    int _day;
  };
}

各位好友，上述实现用到了 堆构建 章节 ------> 向上调整算法与向下调整算法！

注意：>优先级队列 默认使用 Vector 作为其底层存储数据的容器，在 Vector 上又使用了堆算法 ,

对 Vector 元素构成 堆。因此， Priority_queue （优先级队列）就是堆，所有用到 堆的位置均可以