三、priority_queue模拟实现

priority_queue底层用堆实现，priority_queue的模拟实现只需要对堆进行封装即可。

1.仿函数

priority_queue默认是大堆，那么该如何实现小堆呢？需要先了解仿函数。

（1）概念

仿函数让一个类的使用看上去像个函数。仿函数是在类中实现了一个operator( )，是一个类的对象，这个类就有了类似函数的行为，所以这个类就是一个仿函数类，目的是为了让函数拥有类的性质。

这个类的对象即仿函数，可以当作一般函数去用，只不过仿函数的功能是在一个类中的运算符operator()中实现的，使用的时候把函数作为参进行传递即可。

（2）优点

① 仿函数比函数指针的执行速度快，函数指针通过地址调用，而仿函数是对运算符operator进行自定义来提高调用的效率。

② 仿函数比一般函数灵活，可以同时拥有两个不同的状态实体，一般函数不具备此种功能。

③ 仿函数可以作为模板参数使用，因为每个仿函数都拥有自己的类型。

（3）缺点

① 需要单独实现一个类。

② 定义形式比较复杂。

（4）实现

先看如下函数isLess，它实现了<的比较

1. #include<iostream>
2. 
3. bool isLess(int l, int r)
4. {
5.  return l < r;
6. }
7. 
8. int main()
9. {
10.   cout << isLess(1, 3) << endl;
11. }

如果在一个类里，实现同样功能，Less这个类就变成了仿函数类，它的对象就是一个仿函数

1. struct less
2. {
3.  bool operator()(int l, int r)
4.  {
5.    return l < r;
6.  }
7. };

这个类还可以再完善一下，使用类模板来支持不同类型的数据使用<比较大小

1. template <class T>
2. struct less
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l < r;//<的比较
7.  }
8. };

同样，>的仿函数类也可以实现了：

1. template <class T>
2. struct greater
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l > r;//>的比较
7.  }
8. };

如何使用仿函数呢？

1. int main()
2. {
3.  less<int> lessInt;//定义一个仿函数类对象，参数类型指定为int
4.  std::cout << lessInt(1, 3) << std::endl;//对仿函数的调用等价于std::cout << lessInt.operator()(1, 3) << std::endl;
5. }

priority_queue模板中的less替换成greater就可以实现>的比较了：

1. template <class T, class Container = vector<T>,
2. class Compare = greater<typename Container::value_type> > class priority_queue;

2.堆的插入删除

要对priority_queue插入删除，就是在堆上插入删除，堆在物理上是数组，在逻辑上是一颗完全二叉树。根据【数据结构】堆-C语言版一文回忆一下堆的插入删除相关知识

（1）堆的插入（先插入，再向上调整）

（2）堆的删除（先交换，然后删除，再向下调整）

3.代码实现

priority_queue类默认的Container是vector，是自定义类型。因此priority_queue的构造函数、拷贝构造函数、赋值运算符重载函数、析构函数都不用写，会调vector的默认构造函数、拷贝构造函数、赋值运算符重载函数、析构函数。只需要实现7个函数：仿函数<、仿函数>、push、pop、top、size、empty。

（1）仿函数<

1. template<class T>
2. struct less
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l < r;
7.  }
8. };

（2）仿函数>

1.  template<class T>
2.  struct greater
3.  {
4.    bool operator()(const T& l, const T& r)
5.    {
6.      return l > r;
7.    }
8.  };

（3）push()

1.  template<class T, class Container = vector<T>,class Compare = delia::less<T>>//指定Compare方式是less，按<比较
2.  class priority_queue
3.  {
4.  public:   
5.    //向上调整算法
6.    void AdjustUp(size_t child)
7.    {
8.      Compare com;//定义仿函数类对象
9. 
10.       size_t parent = (child - 1) / 2;//找父亲的位置
11.       while (child > 0)
12.       {
13.         //if (_con[parent] < _con[child])//父亲比孩子小，孩子就要往上提
14.         if (com(_con[parent] , _con[child]))//使用仿函数比较
15.         {
16.           swap(_con[parent], _con[child]);//交换父亲和孩子
17.           child = parent;//父亲变孩子
18.           parent = (child - 1) / 2;//重新计算新孩子的父亲位置
19.         }
20.         else
21.         {
22.           //父亲>=孩子就不用动
23.           break;
24.         } 
25.       }
26.     }
27. 
28.     //插入
29.     void push(const T& x)
30.     {
31.       _con.push_back(x);//尾插到堆
32.       AdjustUp(_con.size() - 1);//向上调整
33.     }
34. 
35. private:
36.     Container _con;
37.   };

（4）pop()

1.    //向下调整算法
2.    void AdjustDown(size_t parent)
3.    {
4.      Compare com;//定义仿函数类对象
5. 
6.      size_t child = 2 * parent + 1;//找孩子位置
7.      while (child < _con.size())
8.      {
9.        //找大孩子
10.         if (child + 1 < _con.size() && _con[child+1] > _con[child])
11.         {
12.           child++;
13.         }
14. 
15.         //if(_con[parent] < _con[child])父亲比孩子小，父亲就要往下挪
16.         if (com(_con[parent], _con[child]))//使用仿函数比较
17.         {
18.           swap(_con[parent], _con[child]);//交换父亲和孩子
19.           parent = child;//孩子变父亲
20.           child = parent * 2 + 1;//重新计算孩子的位置
21.         }
22.         else
23.         {
24.           break;
25.         }
26.       }
27.     }
28. 
29. //删除
30.     void pop()
31.     {
32.       swap(_con[0], _con[_con.size() - 1]);//交换堆顶元素和堆尾元素
33.       _con.pop_back();//删除堆顶元素      
34.       AdjustDown(0);//向下调整算法
35.     }

（5）top()

1.    //返回priority_queue第一个元素，即堆顶元素
2.    T top()
3.    {
4.      return _con[0];
5.    }

（6）size()

1.    //求priority_queue队列中元素个数
2.    size_t size()
3.    {
4.      return _con.size();
5.    }

（7）empty()

1.    //判断priority_queue是否为空
2.    bool empty()
3.    {
4.      return _con.empty();
5.    }

4.完整代码段

018-priority_queue.h

1. #pragma once
2. #include<vector>
3. using namespace std;
4. 
5. namespace delia
6. {
7.  template<class T>
8.  struct less
9.  {
10.     bool operator()(const T& l, const T& r)
11.     {
12.       return l < r;
13.     }
14.   };
15. 
16.   template<class T>
17.   struct greater
18.   {
19.     bool operator()(const T& l, const T& r)
20.     {
21.       return l > r;
22.     }
23.   };
24. 
25.   template<class T, class Container = vector<T>,class Compare = std::less<T>>
26.   class priority_queue
27.   {
28.   public:
29.     //Container默认是vector，自定义类型
30.     //构造函数、拷贝构造函数、赋值运算符重载函数、析构函数都不用写，会调用vector的构造函数和析构函数等
31. 
32. 
33. 
34.     //向上调整算法
35.     void AdjustUp(size_t child)
36.     {
37.       Compare com;//定义仿函数类对象
38. 
39.       size_t parent = (child - 1) / 2;//找父亲的位置
40.       while (child > 0)
41.       {
42.         //if (_con[parent] < _con[child])//父亲比孩子小，孩子就要往上提
43.         if (com(_con[parent] , _con[child]))//使用仿函数比较
44.         {
45.           swap(_con[parent], _con[child]);//交换父亲和孩子
46.           child = parent;//父亲变孩子
47.           parent = (child - 1) / 2;//重新计算新孩子的父亲位置
48.         }
49.         else
50.         {
51.           //父亲>=孩子就不用动
52.           break;
53.         } 
54.       }
55.     }
56. 
57.     //插入
58.     void push(const T& x)
59.     {
60.       _con.push_back(x);//尾插到堆
61.       AdjustUp(_con.size() - 1);//向上调整
62.     }
63. 
64.     //向下调整算法
65.     void AdjustDown(size_t parent)
66.     {
67.       Compare com;//定义仿函数类对象
68. 
69.       size_t child = 2 * parent + 1;//找孩子位置
70.       while (child < _con.size())
71.       {
72.         //找大孩子
73.         if (child + 1 < _con.size() && _con[child+1] > _con[child])
74.         {
75.           child++;
76.         }
77. 
78.         //if(_con[parent] < _con[child])父亲比孩子小，父亲就要往下挪
79.         if (com(_con[parent], _con[child]))//使用仿函数比较
80.         {
81.           swap(_con[parent], _con[child]);//交换父亲和孩子
82.           parent = child;//孩子变父亲
83.           child = parent * 2 + 1;//重新计算孩子的位置
84.         }
85.         else
86.         {
87.           break;
88.         }
89.       }
90.     }
91. 
92.     //删除
93.     void pop()
94.     {
95.       swap(_con[0], _con[_con.size() - 1]);//交换堆顶元素和堆尾元素
96.       _con.pop_back();//删除堆顶元素      
97.       AdjustDown(0);//向下调整算法
98.     }
99. 
100.    //返回priority_queue第一个元素，即堆顶元素
101.    T top()
102.    {
103.      return _con[0];
104.    }
105. 
106.    //求priority_queue队列中元素个数
107.    size_t size()
108.    {
109.      return _con.size();
110.    }
111. 
112.    //判断priority_queue是否为空
113.    bool empty()
114.    {
115.      return _con.empty();
116.    }
117. 
118.  private:
119.    Container _con;
120.  };
121. 
122. }

018-test.cpp

1. #include "018-priority_queue.h"
2. #include<iostream>
3. 
4. void test_priority_queue()
5. {
6.  delia::priority_queue<int> pq;
7.  pq.push(9);
8.  pq.push(26);
9.  pq.push(31);
10.   pq.push(3);
11.   pq.push(11);
12.   pq.push(1);
13.   pq.push(5);
14.   pq.push(39);
15.   pq.push(23);
16.   pq.push(18);
17. 
18.   std::cout << "priority_queue:" << std::endl;
19.   while (!pq.empty())
20.   {
21.     std::cout << pq.top() << std::endl;
22.     pq.pop();
23.   }
24.   std::cout << std::endl;
25. }
26. 
27. void test_priority_queue_push()
28. {
29.   delia::priority_queue<int> pq;
30.   pq.push(9);
31.   pq.push(26);
32.   pq.push(31);
33.   pq.push(3);
34.   pq.push(11);
35.   pq.push(1);
36.   pq.push(5);
37.   pq.push(39);
38.   pq.push(23);
39.   pq.push(18);
40. 
41.   pq.push(83);
42. 
43.   std::cout << "push:" << std::endl;
44.   while (!pq.empty())
45.   {
46.     std::cout << pq.top() << std::endl;
47.     pq.pop();
48.   }
49.   std::cout << std::endl;
50. }
51. 
52. void test_priority_queue_pop()
53. {
54.   delia::priority_queue<int> pq;
55.   pq.push(9);
56.   pq.push(26);
57.   pq.push(31);
58.   pq.push(3);
59.   pq.push(11);
60.   pq.push(1);
61.   pq.push(5);
62.   pq.push(39);
63.   pq.push(23);
64.   pq.push(18);
65. 
66.   std::cout << "pop:" << std::endl;
67.   pq.pop();
68.   while (!pq.empty())
69.   {
70.     std::cout << pq.top() << std::endl;
71.     pq.pop();
72.   }
73.   std::cout << std::endl;
74. }
75. 
76. void test_priority_queue_top()
77. {
78.   delia::priority_queue<int> pq;
79.   pq.push(9);
80.   pq.push(26);
81.   pq.push(31);
82.   pq.push(3);
83.   pq.push(11);
84.   pq.push(1);
85.   pq.push(5);
86.   pq.push(39);
87.   pq.push(23);
88.   pq.push(18);
89. 
90.   std::cout << "top:" << std::endl;
91.   std::cout << pq.top() << std::endl;
92.   std::cout << std::endl;
93. }
94. 
95. void test_priority_queue_size()
96. {
97.   delia::priority_queue<int> pq;
98.   pq.push(9);
99.   pq.push(26);
100.  pq.push(31);
101.  pq.push(3);
102.  pq.push(11);
103.  pq.push(1);
104.  pq.push(5);
105.  pq.push(39);
106.  pq.push(23);
107.  pq.push(18);
108. 
109.  std::cout << "size:" << std::endl;
110.  std::cout << pq.size() << std::endl;
111.  std::cout << std::endl;
112. }
113. 
114. void test_priority_queue_empty()
115. {
116.  delia::priority_queue<int> pq;
117.  pq.push(9);
118.  pq.push(26);
119.  pq.push(31);
120.  pq.push(3);
121.  pq.push(11);
122.  pq.push(1);
123.  pq.push(5);
124.  pq.push(39);
125.  pq.push(23);
126.  pq.push(18);
127. 
128.  std::cout << "empty:" << std::endl;
129.  std::cout << pq.empty() << std::endl;
130.  std::cout << std::endl;
131. }
132. 
133. int main()
134. {
135.  test_priority_queue();
136.  test_priority_queue_push();
137.  test_priority_queue_pop();
138.  test_priority_queue_top();
139.  test_priority_queue_size();
140.  test_priority_queue_empty();
141. 
142.  return 0;
143. 
144. }

运行结果如下

【C++】-- STL容器适配器之priority_queue（二）