优先级队列与仿函数

简介: 优先级队列与仿函数

优先级队列

优先级队列 priority_queue 是一种容器适配器,听起来是队列,其实它的底层数据结构是堆,所谓的优先级为默认越大的数优先级越高,即默认为大堆。

使用方式如下面的代码:

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

其中前三行实例化的对象是等价的,都是建大堆,即 class Container 的默认适配容器是 vector,class Compare 默认的仿函数是 less,只有传了默认适配器后才能传仿函数类或类模板。

仿函数 less(return x < y) 在堆的排序算法中比较部分起的作用是建大堆,greater (return x > y)在堆的排序算法中是建小堆,这与日常认知恰好相反。

优先级队列的底层是堆,那么它的插入和删除的时间复杂度就和堆一样,为 O(logN)

仿函数

仿函数的使用可以使优先级队列的使用者随意控制大小堆,通过参数来传递

所谓仿函数,其实是一个类,但它实例化出的对象可以像函数一样去使用,这个功能在C++中其实是为了替换函数指针的,那么它到底是咋样的?

那么在这,它就起到了比较两个数大小的作用

当然,它也可以配合模板来使用

那么,这么简单的功能,如何在优先级队列中做到改变大小堆的功能呢?

首先,写两个仿函数的类模板,分别用来作堆中 父亲 大于孩子结点 和 父亲 小于孩子结点的比较,在 priority_queue类的模板中添加一个模板参数,用于接收一个类模板

控制传过去的参数为 Less 和 Greater ,用这个模板参数Compare 接收,Compare实例化出的对象即可起到比较两个数大小的作用。若传过来的参数为 Less类模板,即可判断一个数是否小于另一个数;若传过来的参数为 Greater,即可判断一个数是否大于另一个数。

实例化对象 _com

在比较父子结点大小的时候即可使用

所以,当传递模板参数为 Less 的时候,即可控制堆为大堆;当传递模板参数为 Greater 的时候,即可控制堆为小堆。使用下面的代码来测试:

void test1()
{
  zyb::Priority_queue<int, vector<int>, Less<int>> pq;
  pq.push(1);
  pq.push(9);
  pq.push(4);
  pq.push(3);
  while (!pq.empty())
  {
    cout << pq.top() << ' ';
    pq.pop();
  }
  cout << endl;
  zyb::Priority_queue<int, vector<int>, Greater<int>> p;
  p.push(1);
  p.push(9);
  p.push(4);
  p.push(3);
  while (!p.empty())
  {
    cout << p.top() << ' ';
    p.pop();
  }
  cout << endl;
}
int main()
{
  test1();
  return 0;
}

运行结果如下,成功的通过传递的参数不同建立了大堆和小堆

priority_queue 实现源码

命名空间应该自己定义。

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

从下面官方的定义就可以知道了,为什么传第三个参数的时候,必须先传第二个参数,第二个参数中包含着要比较数据的类型,第三个仿函数模板类型是跟容器里数据类型有关的!

相关文章
|
6月前
|
算法 数据处理 调度
【C++ 优先队列】了解 C++优先队列中操作符重载的实现
【C++ 优先队列】了解 C++优先队列中操作符重载的实现
87 0
|
算法 C++
STL和优先队列
STL和优先队列
|
3月前
|
存储 设计模式 算法
【C++】deque以及优先级队列
【C++】deque以及优先级队列
|
6月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(上)
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
49 1
|
6月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(下)
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
26 0
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(下)
|
6月前
|
存储 安全 Java
优先级队列
优先级队列
|
算法 测试技术 C++
C++:优先级队列模拟实现和仿函数的概念使用
C++:优先级队列模拟实现和仿函数的概念使用
|
6月前
|
存储 C++ 容器
C++ STL学习之【优先级队列】
C++ STL学习之【优先级队列】
65 0
C++初识仿函数
C++初识仿函数
|
人工智能 算法 搜索推荐
我学会了,封装自己的优先队列PriorityQueue
优先队列本身就是一种队列。 普通队列:先进先出、后进后出,如排队买票吃饭一样。 优先队列:出队顺序和入队顺序无关,和优先级相关。如去医院看病,床位非常的紧张,需要排队才能去做手术的话,此时做手术的这个队伍的顺序就是一个优先队列。因为医生是根据每一个患者的病症的不同以及需要这个手术的紧急程度的不同来去安排谁先做手术谁后做手术,也可以认为每一个患者是有一个优先级的。优先级高者先得,这样的一个队列就叫做优先队列,它和普通队列最主要的区别是在于出队这个操作上,入队很简单,但是优先级高的先出队。
229 0
我学会了,封装自己的优先队列PriorityQueue