C++ priority_queue 与 deque 使用及模拟实现

对于它是如何在默认小于比较的情况下实现大堆的，我们后面的模拟实现会进一步说明。

2. 如果在 priority_queue 中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

class Date{
    friend ostream& operator<<(ostream& _cout, const Date& d);
public:
    Date(int year = 1900, int month = 1, int day = 1) : _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);
    }
    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;
};

ostream& operator<<(ostream& _cout, const Date& d){
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

void test2(){
    // 大堆，需要用户在自定义类型中提供<的重载
    priority_queue<Date> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
    
    // 如果要创建小堆，需要用户提供>的重载
    priority_queue<Date, vector<Date>, greater<Date>> q2;
    q2.push(Date(2018, 10, 29));
    q2.push(Date(2018, 10, 28));
    q2.push(Date(2018, 10, 30));
    cout << q2.top() << endl;
}

int main(){
    test2();
    return 0;
}

有兴趣可以练习一下 LeetCode 上的 数组中的第 K 个最大元素。

1.3 模拟实现

接下来我们模拟实现一下，在此之前，我们要对于堆这种数据结构有所了解。那咱们就步入正题，对于 priority_queue 的实现其实就是将堆进行一定的封装。

#pragma once
#include <vector>
#include <algorithm>
#include <utility>

// 优先队列模板类
// T: 元素类型，Container: 底层容器类型 (默认 vector), Compare: 比较器类型 (默认 less<T>)
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
public:
    // 默认构造函数
    priority_queue() {}

    // 向下调整算法 (堆化)
    // 用于维护堆性质，当某个节点不满足堆性质时，将其向下调整
    // a: 容器引用，n: 堆的大小，root: 要调整的根节点下标
    void AdjustDown(Container& a, int n, int root) {
        int parent = root;
        int child = parent * 2 + 1; // 左孩子
        while (child < n) {
            // 如果右孩子存在且比左孩子大 (对于大堆)，选择较大的孩子
            if (child + 1 < n && _comp(a[child], a[child + 1])) {
                ++child; // 选择右孩子
            }
            // 如果父节点小于孩子节点 (对于大堆)，需要交换
            if (_comp(a[parent], a[child])) {
                swap(a[child], a[parent]);
                parent = child; // 继续向下调整
                child = parent * 2 + 1; // 新的左孩子
            } else {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 向上调整算法
    // 用于在插入新元素后维护堆性质，从叶子节点向上调整
    // child: 新插入元素的下标
    void AdjustUp(int child) {
        int parent = (child - 1) / 2; // 计算父节点下标
        while (child > 0) {
            // 如果父节点小于孩子节点 (对于大堆)，需要交换
            if (_comp(_c[parent], _c[child])) {
                swap(_c[child], _c[parent]);
                child = parent; // 继续向上调整
                parent = (child - 1) / 2; // 新的父节点
            } else {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 使用迭代器范围构造优先队列
    // first: 起始迭代器，last: 结束迭代器
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last) : _c(first, last) {
        int size = _c.size();
        // 从最后一个非叶子节点开始，向前逐个向下调整建堆
        int i = (size - 2) / 2; // 最后一个非叶子节点的下标
        while (i >= 0) {
            AdjustDown(_c, last - first, i);
            i--;
        }
    }

    // 判断优先队列是否为空
    bool empty() const {
        return _c.empty();
    }

    // 返回优先队列中元素个数
    size_t size() const {
        return _c.size();
    }

    // 返回堆顶元素 (非 const 版本)
    T& top() {
        return _c[0]; // 堆顶元素总是在容器首部
    }

    // 返回堆顶元素 (const 版本)
    const T& top() const {
        return _c[0];
    }

    // 插入新元素
    void push(const T& x) {
        _c.push_back(x); // 在尾部插入新元素
        AdjustUp(_c.size() - 1); // 从新插入的位置向上调整
    }

    // 删除堆顶元素
    void pop() {
        swap(_c[0], _c[_c.size() - 1]); // 将堆顶元素与最后一个元素交换
        _c.pop_back(); // 删除原来的堆顶元素 (现在在尾部)
        AdjustDown(_c, _c.size(), 0); // 从新的堆顶位置向下调整
    }

private:
    Container _c; // 底层容器，用于存储堆元素
    Compare _comp; // 比较器对象，用于元素比较
};

对于堆比较了解的我们来说，实现很简单，这里我们就主要再来说明一下它为什么小于是大堆：

二、deque

2.1 介绍

在上篇文章中，我们对于 stack 与 queue 的模拟实现的时候底层容器其采用的是 vector，我也提到，底层并未用 vector 作为默认容器，而是 deque（双端队列）。

deque(双端队列)：是一种双开口的连续空间的数据结构。 双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

那么 deque 到底是怎么实现的呢？难道 deque 是一块连续的空间，然后怎么样怎么样……

其实，**deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组。**其底层结构如下图所示：

可见，双端队列底层采用分段存储的方式，实际内存是不连续的。所以为了给用户提供连续空间和随机访问的错觉，deque 的迭代器承担了屏蔽底层复杂性的重任。

我们可以来看一下 deque 的迭代器实现，如下图：

解释：

我们可以看出，中控器其实是一个指针数组，每个指针指向一个缓冲区，当缓冲区不够时可以动态增长。迭代器的指针：

• cur: 指向当前元素
• first: 指向当前缓冲区的起始位置
• last: 指向当前缓冲区的结束位置
• node: 指向中控器中当前缓冲区对应的指针

那 deque 是如何借助其迭代器维护其假想连续的结构呢？

其实，在 deque 的底层，除了中控数组以外，还有两个迭代器，start 与 finish 迭代器。如下图：

这样，在对于头插和头删以及尾插、尾删的时候，就会很快 O(1)。

这样一看，deque 与 vector 比较，deque 的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。 与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

deque 的核心特点就是：

• 头尾插入删除时间复杂度 O(1)
• 支持随机访问，但效率低于 vector
• 底层采用'中控器 + 缓冲区'的分段存储方式

但是，它也是有缺陷的。

2.2 缺陷

尽管 deque 功能强大，但也有明显缺陷：

1. 随机访问效率较低（需要计算缓冲区位置）
2. 迭代器失效规则复杂
3. 内存使用效率不如 vector
4. 缓存局部性较差

因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。

三、STL 标准库中对于 stack 和 queue 的模拟实现

3.1 为什么选择 deque 作为 stack 和 queue 的底层默认容器

stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以； queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list。

但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：

stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。

结合了 deque 的优点，而完美的避开了其缺陷。 下面我们就仿照标准库来进行 stack 和 queue 的模拟实现。

3.2 stack 的模拟实现

#include <deque>

template<class T, class Con = deque<T>>
class stack {
public:
    stack() {}
    void push(const T& x) { _c.push_back(x); }
    void pop() { _c.pop_back(); }
    T& top() { return _c.back(); }
    const T& top() const { return _c.back(); }
    size_t size() const { return _c.size(); }
    bool empty() const { return _c.empty(); }
private:
    Con _c;
};

3.3 queue 的模拟实现

#include <deque>

template<class T, class Con = deque<T>>
class queue {
public:
    queue() {}
    void push(const T& x) { _c.push_back(x); }
    void pop() { _c.pop_front(); }
    T& back() { return _c.back(); }
    const T& back() const { return _c.back(); }
    T& front() { return _c.front(); }
    const T& front() const { return _c.front(); }
    size_t size() const { return _c.size(); }
    bool empty() const { return _c.empty(); }
private:
    Con _c;
};