C++ ——>std :: priority_queue - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

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

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

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

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

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

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

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

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

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

//priority__模拟实现

#include 
#include 
#include 

using std :: cout;
using std :: endl;
using std :: vector;
using std :: swap;
    
namespace UC
{
  template>
	class priority_queue
  {
    private:
    
    //向下调整
    void AdjustDown(int parent)
    {
      int child = parent * 2 + 1;
      while(child  0)
      {
      	if(_con[parent] 
    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 T;
  
  T.push(12);
  T.push(13);
  T.push(16);
  T.push(17);
  
  T.push(21);
  T.push(23);
  
  while(!T.empty())
  {
  	cout

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

————–>”PriorityQueue.h”

———–>“Test.cpp”

————–>”PriorityQueue.h” ——->升级版

——–>仿函数与自定义类型: >

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

#include 
#include 
#include 
#include 

using std :: cout;
using std :: endl;
using std 服务器托管网:: vector;
using std :: swap;

//仿函数
template
  struct Less
  {
  	bool operator()(const T& x, const T& y)
    {
    	return x 
  struct Greater
  {
  	bool operator()(const T& x, const T& y)
    {
    	return x > y;
    }
  };
    
namespace UC
{
  template, class Compare = Less>
	class priority_queue
  {
    private:
    
    //向下调整
    void AdjustDown(int parent)
    {
      Compare com;
      int child = parent * 2 + 1;
      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
    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);
    }
    
    private:
    
    int _year;
    int _month;
    int _day;
  };
}

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

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

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