【C++】学习笔记——优先级队列-阿里云开发者社区

十、优先级队列

1. priority_queue的介绍

优先级队列 其实也不属于队列，它跟 stack 和 queue 一样，都是 容器适配器 。

优先级队列的默认适配容器是 vector 。要使用优先级队列的话，需要包含 queue 头文件。

优先级队列的接口也非常简单明了，我们来简单试一下：

#include<iostream>
// 包含 queue 头文件
#include<queue>
using namespace std;
int main()
{
  priority_queue<int> pq;
  pq.push(3);
  pq.push(1);
  pq.push(4);
  pq.push(2);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
  return 0;
}

我们插入的数据是 3 1 4 2 ，打印出来的数据却是 4 3 2 1 ，竟然将其排了个降序，这有点像我们之前学过的一种数据结构啊。是的，它很像堆，它底层其实就是大根堆。优先级队列 就是按优先级取数据，堆顶数据就是优先级最高的。

2. 优先级队列如何使小的数据优先级高

优先级队列默认是大根堆，大的数据优先级高，那么我们该如何使小的数据优先级高呢？就是使优先级队列以小根堆的形式实现。答案嘛，就涉及到 STL 的另一个组件了—— 仿函数。

优先级队列 模板的第三个参数就是仿函数，默认是 less （小于），如果要使其成 小根堆 的形式，则需要将其参数修改为 greater （大于），由于缺省参数不能跳跃着传，所以需要将前面两个参数都给加上才行。

// 三个参数
priority_queue<int, vector<int>, greater<int>> pq;

我们来使用一下：

#include<iostream>
#include<queue>
using namespace std;
int main()
{
  priority_queue<int, vector<int>, greater<int>> pq;
  pq.push(3);
  pq.push(1);
  pq.push(4);
  pq.push(2);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
  return 0;
}

在其他有这种仿函数的函数中，less 默认都是排升序，greater 都是排降序，比如 sort 函数 ，而 优先级队列 中，less 是大根堆， greater 是小根堆。

// sort 排降序
sort(v.begin(), v.end(), greater<int>());

注意，sort 函数 的第三个参数是函数参数，需要传对象，所以末尾带着 () 来创建匿名对象，而 优先级队列 则是类模板，传类型，不需要带 () 。

3. 仿函数介绍

仿函数其实是一个类型，一种结构。

struct Less
{
  // 重载 ()
  bool operator()(const int& x, const int& y)
  {
    return x < y;
  }
};

我们要怎样使用这个类呢？

int main()
{
  Less Lessfunc;
  cout << Lessfunc(1, 2) << endl;
  // 上面写法本质上是下面写法
  cout << Lessfunc.operator()(1, 2) << endl;
  return 0;
}

大家有没有发现，上面的写法 很像函数 啊，Lessfunc 就像函数名一样，但是没想到其实他是对象名。所以仿函数就是对象很像函数的类型。把模板套上就可以使类型泛型。

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

所以在 sort 函数 里的第三个参数，greate< int >() 就是一个匿名对象，类型是 int ，调用重载 () 符号。

4. priority_queue的模拟实现

先把简单的框架搭好，再来挨个实现。由于 STL库 里的 priority_queue 是位于 queue 头文件里，所以我们这里头文件取名为 Queue.h 。

// Queue.h
#pragma once
namespace my
{
  template<class T, class Container = vector<T>>
  class priority_queue
  {
  public:
    void push(const T& x)
    {
    }
    void pop()
    {
    }
    bool empty()
    {
    }
    size_t size()
    {
    }
    const T& top()
    {
    }
  private:
    Container _con;
  };
}

我们来想一想，我们的堆是如何插入数据的：堆是尾部插入数据，然后向上调整位置 。那堆是如何删除数据的呢？堆是收尾交换数据，然后尾删，最后将堆顶数据向下调整 。

#pragma once
namespace my
{
  template<class T, class Container = vector<T>>
  class priority_queue
  {
  public:
    adjust_up(size_t child)
    {
    }
    adjust_down(size_t parent)
    {
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void pop()
    {
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
    const T& top()
    {
      return _con[0];
    }
  private:
    Container _con;
  };
}

向上调整函数注意的就是什么情况可以向上调整，当孩子的值比父亲大时，需要将孩子的位置与父亲的位置进行交换 ，然后更新孩子和父亲的下标。那什么时候结束调整呢？当孩子的值比不父亲的值大，或者孩子已经到堆顶位置 此时需要结束调整。

adjust_up(size_t child)
{
  size_t parent = (child - 1) / 2;
  while (child > 0)
  {
    if (_con[child] > _con[parent])
    {
      // 交换数据
      std::swap(_con[child], _con[parent]);
      // 更新下标
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    { 
      break;
    }
  }
}

向下调整需要注意的是，父节点要是最大的值，所以要交换也是与最大的孩子交换，第一步需要找到最大的孩子 ，然后 判断父亲是否比孩子小，小则交换，最后判断结束条件 父节点已经不再比最大的孩子小或者，已经到达叶子节点 则退出。

adjust_down(size_t parent)
{
  size_t child = parent * 2 + 1;
  // 左孩子孩子存在
  while (child < _con.size())
  {
    // 右孩子存在且比左孩子大
    if (child + 1 < _con.size() && _con[child + 1] > _con[child])
    {
      ++child;
    }
    if (_con[parent] < _con[child])
    {
      // 交换
      std::swap(_con[parent], _con[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

除了仿函数外，我们的代码已经实现到了：

// Queue.h
#pragma once
#include<vector>
namespace my
{
  template<class T, class Container = vector<T>>
  class priority_queue
  {
  public:
    void adjust_up(size_t child)
    {
      size_t parent = (child - 1) / 2;
      while (child > 0)
      {
        if (_con[child] > _con[parent])
        {
          std::swap(_con[child], _con[parent]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        { 
          break;
        }
      }
    }
    void adjust_down(size_t parent)
    {
      size_t child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && _con[child + 1] > _con[child])
        {
          ++child;
        }
        if (_con[parent] < _con[child])
        {
          std::swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void pop()
    {
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
    const T& top()
    {
      return _con[0];
    }
  private:
    Container _con;
  };
}

// test.cpp
#include<iostream>
#include"Queue.h"
using namespace std;
int main()
{
  my::priority_queue<int> pq;
  pq.push(1);
  pq.push(3);
  pq.push(4);
  pq.push(2);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
  return 0;
}

OK，这里默认大堆就已经完成了。但是我们这个代码并不能控制变成小堆，我们需要使用仿函数来控制比较逻辑。

// 在 my 命名空间内
template<class T>
class less
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
template<class T>
class greater
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
};

有了仿函数，所以我们的优先级队列模板参数就要将其加上。

// 默认大根堆，第三个参数默认是仿函数 less
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
  //
private:
  //
};

所以，类里的比较大小的判断就可以使用仿函数来调用对象来实现。

void adjust_up(size_t child)
{
  // 这里
  Compare com;
  size_t parent = (child - 1) / 2;
  while (child > 0)
  {
    // _con[parent] < _con[chlid]
    if (com(_con[parent], _con[child]))
    {
      std::swap(_con[child], _con[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    { 
      break;
    }
  }
}
void adjust_down(size_t parent)
{
  // 这里
  Compare com;
  size_t child = parent * 2 + 1;
  while (child < _con.size())
  {
    // _con[child] < _con[child + 1]
    if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
    {
      ++child;
    }
    //_con[parent] < _con[child]
    if (com(_con[parent], _con[child]))
    {
      std::swap(_con[parent], _con[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

测试一下：

#include<iostream>
#include"Queue.h"
using namespace std;
int main()
{
  // 大堆
  my::priority_queue<int> pq;
  pq.push(1);
  pq.push(3);
  pq.push(4);
  pq.push(2);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
  // 小堆
  my::priority_queue<int, vector<int>, greater<int>> pq2;
  pq2.push(1);
  pq2.push(3);
  pq2.push(4);
  pq2.push(2);
  while (!pq2.empty())
  {
    cout << pq2.top() << " ";
    pq2.pop();
  }
  cout << endl;
  return 0;
}

可以。

补：反向迭代器

反向迭代器其实可以通过修改正向迭代器来达到目的，但是我们要求代码复用，所以需要用另一种方法来实现反向迭代器。此时我们可以使用迭代器适配器来实现所有容器的反向迭代器。你给我一个容器的正向迭代器，我来帮你实现其反向迭代器。

反向迭代器和正向迭代器的不同点在哪？功能类似，++和–方向不一样。

其中反向迭代器的模板部分代码就如下所示，只需要注意反向迭代器要正确调用正向迭代器的函数就能成功实现。比如：++调用–，–调用++。

#pragma once
namespace me
{
  template<class Iterator, class Ref, class Ptr>
  class ReverseIterator
  {
  public:
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;
    Iterator _it;
    
    ReverseIterator(Iterator it)
      :_it(it)
    {}
    Ref operator*()
    {
      Iterator tmp = _it;
      return *(--tmp);
    }
    Ptr operator->()
    {
      return &(operator*());
    }
    // 前置++
    Self& operator++()
    {
      --_it;
      return *this;
    }
    // 前置--
    Self& operator--()
    {
      ++_it;
      return *this;
    }
    bool operator!=(const Self& s)
    {
      return _it != s._it;
    }
  };
}

【C++】学习笔记——优先级队列

十、优先级队列

1. priority_queue的介绍

2. 优先级队列如何使小的数据优先级高

3. 仿函数介绍

4. priority_queue的模拟实现

补：反向迭代器

未完待续

热门文章

最新文章

相关课程

相关电子书

【C++】学习笔记——优先级队列

十、优先级队列

1. priority_queue的介绍

2. 优先级队列如何使小的数据优先级高

3. 仿函数介绍

4. priority_queue的模拟实现

补： 反向迭代器

未完待续

热门文章

最新文章

相关课程

相关电子书

补：反向迭代器