『C++ - STL』之优先级队列( priority_queue )

前言

什么是优先级队列，从该名中可以知道他一定有队列的一定属性，即先入先出(LILO)，而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队，这就是优先级队列；
而在数据结构中有一个支持该操作的结构 - 堆( heap );
而在STL中，这个优先级队列( priority_queue )也正是堆；

---

优先级队列的结构

既然优先级队列的结构是堆，那想必结构上也不难；
堆的结构是以顺序表为基础，从而实现完全二叉树的结构；

从该容器的接函数接口中也可以知道实际上它就是个堆；

---

优先级队列的模拟实现

优先级队列priority_queue为一个类模板容器；
且同STL中的栈stack与队列queue一样都为适配器模式的容器，即以某个容器为基础；

template ,class Compare = less > class priority_queue;
其模板参数有三个分别为：

• class T
  容器所存储的数据类型 T ；

• class Container = vector
  容器适配器且定缺省参数默认为 vector< T >；

• class Compare = less
  一个用来比较大小的仿函数，给定缺省参数默认为 less ，该仿函数在标准库std中；

根据文档中的信息来看，优先级队列主要的几个接口也正是数据结构中堆应有的结构；

#pragma once 

#include

#include

#include

using namespace std;

namespace my_priority{//命名空间


  template<class T,class Container = std::vector<T>>//暂未设置仿函数

    class priority_queue{//总体框架
 public:
        void push(const T& val){//增
          _con.push_back(val);
          adjust_up(_con.size()-1);
        }

        void pop(){
          
          std::swap( _con[_con.size()-1],_con[0]);//删
          _con.pop_back();
          adjust_down(0);

        }

        bool empty(){//判空

          return _con.empty();
        }

        size_t size(){//返回大小

          return _con.size();
        }

        const T& top()const{//返回堆顶

          assert(!_con.empty());
          return _con[0];
 }

        void swap(priority_queue& con){//交换
          if(_con!=con._con)
          _con.swap(con._con);
        }

      private:

	//必要函数 - 向上调整&&向下调整

        void adjust_up(size_t child){
          size_t parent = child;
          while(parent>0){
            parent = (child-1)/2;
            if(_con[parent]<_con[child]){
              std::swap(_con[parent],_con[child]);
            }
            child = parent;
          }

        }

        void adjust_down(size_t parent){
          Compare comfunc;
          size_t child = parent*2+1;
          while(child<_con.size()){
            if(child+1<_con.size()&&_con[child]<_con[child+1]){
              ++child;
            }if(_con[parent]<_con[child]){
              std::swap(_con[parent],_con[child]);
            }
            parent = child;
            child = parent*2+1;
          }
        }

        Container _con; //容器适配器所实例化的对象，当前代码为vector
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

但是在库中，模板参数共有三个，具体的第三个仿函数到底是什么？

---

仿函数

仿函数，也被称为函数对象；
即一个可以使用函数功能的类，本质上就是在类中重载了operator();
举个简单的例子，当我们想要写一个能将两个数进行相加的仿函数即可以这么写；

struct Add{
	int operator()(int a,int b){
		return a+b;
	} 
}
int main()
{
	Add addfunc;
	int ret = addfunc(1,2);//仿函数的调用；
	ret = Add() (1,2);//利用匿名对象；
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

同理，也可以根据该方法写一个比较两个对象大小的仿函数；
为了能接受多种类型的数据进行比较也可以将其设置为类模板；

template<class T>
struct less{
	bool operator()(const T& a,const T& b){
		return a<b;
	} 
1
2
3
4
5

这也就是在实现当中缺失的模板参数，仿函数；
由于优先级队列priority_queue的大小根堆属性是由其中的向上调整算法adjust_up与向下调整算法adjust_down来决定的（建堆以及堆的调整）；所以只要将对应的比较大小><换成仿函数即可；

---

最终代码

#pragma once 

#include

#include

#include

using namespace std;

namespace my_priority{

  template<class T>
    struct less{
      bool operator()(const T& v1,const T& v2){
        return v1<v2;
      }
    };

  template<class T>
    struct greater{
      bool operator()(const T& v1,const T& v2){
        return v1>v2;
      }
    };

  template<class T,class Container = std::vector<T> ,class Compare = less<T>>

    class priority_queue{
 public:
        void push(const T& val){
          _con.push_back(val);
          adjust_up(_con.size()-1);
        }

        void pop(){
          
          std::swap( _con[_con.size()-1],_con[0]);
          _con.pop_back();
          adjust_down(0);

        }

        bool empty(){

          return _con.empty();
        }

        size_t size(){

          return _con.size();
        }

        const T& top()const{

          assert(!_con.empty());
          return _con[0];
 }

        void swap(priority_queue& con){
          if(_con!=con._con)
          _con.swap(con._con);
        }

      private:

        void adjust_up(size_t child){
          Compare comfunc;
          size_t parent = child;
          while(parent>0){
            parent = (child-1)/2;
            if(comfunc(_con[parent],_con[child])){
              std::swap(_con[parent],_con[child]);
            }
            child = parent;
          }

        }

        void adjust_down(size_t parent){
          Compare comfunc;
          size_t child = parent*2+1;
          while(child<_con.size()){
            if(child+1<_con.size()&&comfunc(_con[child],_con[child+1])){
              ++child;
            }if(comfunc(_con[parent],_con[child])){
              std::swap(_con[parent],_con[child]);
            }
            parent = child;
            child = parent*2+1;
          }

        }

        Container _con;
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96