STL 笔记（十一）：容器适配器——优先队列

#include 
#include 

using namespace std;

// 优先队列（堆 - 函数（））

// 1. 封装容器（顺序存储方式）：vector（默认）, deque
// 2. less - 小于交换，值大优先 - 大根堆 | greater - 大于交换，值小优先 - 小根堆
// 3. 优先队列的优先级取决于用于比较的函数（less/greater），而非元素的大小
// 4. 成员函数：构造函数 / empty / size / top / push / pop

void Display(vector v)
{
    for (vector::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;
}

void test1()
{
    // 1. 建堆 make_heap
    int a[] = {5, 4, 1, 12, 9, 8};
    vector v(a, a + 6);
    make_heap(v.begin(), v.end());
    Display(v); // 12 9 8 4 5 1

    // 2. 插入 push_heap
    v.push_back(13);
    push_heap(v.begin(), v.end()); // 12 9 8 4 5 1
    Display(v); // 13 9 12 4 5 1 8

    // 3. 删除 pop_heap
    pop_heap(v.begin(), v.end()); // 在实际中并未将数据删除，仅仅是将最大值置于数组末尾
    Display(v); // 12 9 8 4 5 1 13
    v.pop_back();
    Display(v); // 12 9 8 4 5 1
}

void test2()
{
    priority_queue p1;                            // vector - 大根堆
    priority_queue > p2;               // deque - 大根堆
    priority_queue, greater > p3; // deque - 小根堆

    int a[] = {5, 4, 1, 12, 9, 8};
    vector v(a, a + 6);
    priority_queue p4(less(), v);
    priority_queue p5(v.begin(), v.end());

    deque d(a, a + 6);
    priority_queue, greater > p6(d.begin(), d.end()); // deque - 小根堆

    cout << p6.empty() << endl;
    cout << p6.size() << endl;
    cout << p6.top() << endl; // 1 优先级最高

    p6.push(13);

    // 遍历出队列
    while(!p6.empty()) {
        cout << p6.top() << ' '; // 升序 1 4 5 8 9 12 13
        p6.pop();
    }
}

int main()
{
    test1();
    test2();

    return 0;
}

#include 
#include 
#include 
#include 

using namespace std;

// 学生信息（姓名、语文、数学、总成绩）
// 输出时，按照总成绩由高到底排序 | 如果总成绩相同，按语文成绩排序

class Student
{
private:
    string stuName;
    double lScores;
    double mScores;
    double total;
public:
    Student(string n, double l, double m)
    {
        stuName = n;
        lScores = l;
        mScores = m;
        total = l + m;
    }
    void stuShow() const // 常对象只能访问常成员函数
    {
        cout << stuName << 't' << lScores << 't' << mScores << 't' << total << endl;
    }
    bool operator<(Student s) const // 常对象只能访问常成员函数
    {
        if (total == s.total) {
            return lScores < s.lScores;
        }
        return total < s.total;
    }
    bool operator>(Student s) const
    {
        if (total == s.total) {
            return lScores > s.lScores;
        }
        return total > s.total;
    }
};

int main()
{
    Student s[] = {
        Student("Reyn", 93, 90),
        Student("Lisa", 95, 90),
        Student("Jhon", 90, 95)
    };

    priority_queue p(s, s + 3); // 仿函数【less|greater】中的参数均为常量类型

    // 重载>操作符，利用【greater】仿函数初始化优先队列，以分数从小到大排列
    // priority_queue, greater > p(s, s + 3);

    cout << "StuNAME" << 't' << "LSCORE" << 't' << "MSCORE" << 't' << "TOTAL" << endl;

    while(!p.empty()) {
        p.top().stuShow();
        p.pop();
    }

    return 0;
}

• 优先队列是一个容器适配器，由于其数据结构是堆，所以其封装的序列型容器为数组，即 vector 与 deque，其中 vector 是默认的
• 优先队列是按照某一个优先级来排序的，优先级通过函数来体现（而非元素的大小），一般为 less 和 greater，除此之外，还应注意其底层的实现是使用了与堆相关的函数，例如 make_heap，pop_heap 等
• less - 小于交换，值大优先 - 大根堆 | greater - 大于交换，值小优先 - 小根堆，根据建堆的过程，在两数相比较的过程中，对于每一个子树中的根节点来说，如果使用 less 函数，则是选择子树中最大的值作为新的根节点（因为小于，满足 less 就会交换），所以最终数值最大的会成为树的根节点，从而构造了大根堆，greater 类似
• 在案例中，Student 类型中的部分函数被标识了 const（常函数），这是因为仿函数【less|greater】中的参数均为常量类型，而常对象只能访问常成员函数

在下一篇文章，我们将介绍 C++ 中的关联性容器——集合

此文章主要用来作为课程学习过程中的总结，大家如果有什么问题也可以在评论区留言，我会尽力帮大家解决问题，如果觉得对大家有帮助的话，希望多多点赞、转发，谢谢！