STL中的优先级队列

1.引言

2.简介

3.基本操作

4.实现原理

5.自定义优先级比较

6.相关题目

7.能特点

8.总结

1.引言

在C++标准库中，优先级队列是一种非常有用的数据结构，它允许我们根据元素的优先级来对其进行排序和访问。这种数据结构在多种应用场景中都发挥着重要作用，如任务调度、路由算法、图形算法等。本文将深入探讨C++中优先级队列的实现原理、使用方法以及性能特点。

2.简介

优先级队列（Priority Queue）是一种数据结构，其中每个元素都有一个与之关联的“优先级”。在优先级队列中，元素的排列顺序是根据它们的优先级来确定的，而不是它们进入队列的顺序。通常情况下，优先级最高的元素会最先出队。

C++标准库中的priority_queue容器就是一个典型的优先级队列实现。它是一个拥有权值观念的队列，其元素的排列顺序并不是按照插入顺序，而是根据每个元素所关联的优先级（权值）来确定的。默认情况下，priority_queue使用<操作符对元素进行比较，因此优先级最高的元素将位于队列的顶部。

大堆

vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int, vector<int>, less<int>> pq(v.begin(), v.end());
//priority_queue<int, vector<int>> pq(v.begin(), v.end());  //写法一样

小堆

vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.end());  //生成小堆

3.基本操作

C++中的priority_queue提供了以下基本操作：

push()：向优先级队列中添加一个元素。
top()：返回优先级队列中优先级最高的元素（即队首元素），但不会删除该元素。
pop()：删除优先级队列中优先级最高的元素（即队首元素）。
size()：返回优先级队列中的元素数量。
empty()：检查优先级队列是否为空。
emplace() : 构造并插入一个元素

下面是一个简单的示例代码，展示了如何使用priority_queue：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 创建一个空的优先级队列
    priority_queue<int> pq;
    
    // 向优先级队列中添加元素
    pq.push(3);
    pq.push(5);
    pq.push(1);
    pq.push(4);
    
    // 输出优先级队列的大小和队首元素
    cout << "Size of priority queue: " << pq.size() << endl;
    cout << "Top element: " << pq.top() << endl; // 输出5，因为5是优先级最高的元素
    
    // 删除队首元素并输出剩余元素的大小和队首元素
    pq.pop();
    cout << "Size after pop: " << pq.size() << endl;
    cout << "Top element after pop: " << pq.top() << endl; // 输出4，现在是优先级最高的元素
    
    return 0;
}

4.实现原理

在C++标准库中，priority_queue通常是基于堆（Heap）数据结构来实现的。堆是一种特殊的树形数据结构，它满足堆属性：即任意节点都小于或等于（在最大堆中）或大于或等于（在最小堆中）其子节点。在priority_queue中，默认情况下使用的是最大堆，因此优先级最高的元素（即值最大的元素）总是位于堆的顶部。

当向优先级队列中添加一个新元素时，该元素会被插入到堆的末尾，然后通过“上浮”（Percolate Up）操作来重新调整堆的结构，以确保其满足堆属性。同样地，当从优先级队列中删除元素时（通常是删除优先级最高的元素），堆会通过“下沉”（Percolate Down）操作来重新调整其结构。

5.自定义优先级比较

默认情况下，priority_queue使用<操作符对元素进行比较，以确定它们的优先级。然而，有时我们可能需要根据特定的比较逻辑来定义元素的优先级。为此，我们可以向priority_queue传递一个自定义的比较函数或函数对象。

下面是一个示例代码，展示了如何使用自定义的比较函数来创建一个最小堆（即优先级最低的元素位于堆顶）：

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于std::greater<int>
using namespace std;

int main() {
    // 使用自定义的比较函数（std::greater<int>）来创建一个最小堆
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    // 向最小堆中添加元素
    min_heap.push(3);
    min_heap.push(1);
    min_heap.push(4);
    min_heap.push(1); // 允许重复元素
    min_heap.push(5);
    
    // 输出最小堆的队首元素（即优先级最低的元素）
    cout << "Top element of min_heap: " << min_heap.top() << endl; // 输出1，因为1是优先级最低的元素（值最小）
    
    return 0;
}

6.相关题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2：

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

题目中有要求，必须设计时间复杂度为O(N)的算法。那么先进行排序操作的同学就另寻他路吧。这道题就可以用到优先级队列，就是堆。先把堆建好，然后pop k-1次后的堆顶就是第k大的元素。

class Solution 
{
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        while(--k)
        {
             pq.pop();
        }
        return pq.top();
    }
};

7.能特点

由于priority_queue是基于堆来实现的，因此其插入和删除操作的时间复杂度都是O(log n)，其中n是队列中的元素数量。这使得priority_queue在处理大量数据时仍然能够保持较高的性能。然而，需要注意的是，由于堆的结构特点，访问队列中的非队首元素需要遍历整个队列，因此其时间复杂度为O(n)。在实际应用中，我们通常只关心优先级最高的元素（即队首元素），因此这个限制通常不会成为问题。