STL priority_queue（优先队列）详解

什么是 STL priority_queue？

STL priority_queue 是一种基于堆的数据结构，用于实现优先队列，即能够按照特定的优先级顺序（默认为大顶堆）存储和访问元素。它是一个模板类，可以存储任何类型的数据，保证了插入元素和删除元素的时间复杂度都为 $O(logN)$。

如何使用 STL priority_queue？

我们可以通过以下代码定义一个 STL priority_queue：

priority_queue<int> pq;

这行代码定义了一个存储 int 类型数据的空优先队列。我们可以用以下代码向其中插入元素：

pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);

以上代码中，push 操作用于向优先队列中插入元素。因为默认情况下优先队列采用的是大顶堆，所以以上代码会在优先队列中创建一个如下的堆：

         4
        / \
       3   1
      /
     1

接下来，我们可以用以下代码访问队首元素并删除它：

int top = pq.top();
pq.pop();

这段代码将访问队首元素 4，将其从队列中删除，并将其赋值给 top 变量。执行完成后，优先队列中剩余的元素为：

         3
        / 
       1    
      /
     1

我们称这个操作为弹出栈顶元素。

优先级定制

默认情况下，优先队列采用的是大顶堆排序，即根据元素的大小来进行排序。但是，我们也可以自定义优先级排序方式，以实现我们特定的需求。

假设我们需要存储一个有编号和重要性的任务列表，并按照重要性进行排序。我们可以通过以下代码定义一个包含任务信息的结构体：

struct Task {
    int id;
    int importance;
    bool operator<(const Task& t) const {
        return importance < t.importance;
    }    
};

该结构体中包含任务编号和重要性属性，并通过重载小于号运算符实现了自定义的比较方式。

接下来，我们可以通过以下代码定义一个存储 Task 类型数据的优先队列，并向其中插入几个任务：

priority_queue<Task> taskList;
taskList.push({1, 5});
taskList.push({2, 3});
taskList.push({3, 9});
taskList.push({4, 7});

假设以上任务列表中任务编号为 3 的任务的重要性最高，我们可以使用以下代码访问并弹出队首元素，即取出编号为 3 的任务：

Task topTask = taskList.top();
taskList.pop();

执行完以上代码后，topTask 结构体中的值为 {3, 9}，任务列表中剩余元素为：

{4, 7}
{1, 5}
{2, 3}

由此可见 STL priority_queue 具有非常高的可扩展性，开发者可以根据实际需求灵活运用此数据结构。

示例说明

示例一：求数据流中的中位数

假设有一组数据流，需要求这个数据流中的中位数，即中间位置的数。我们可以通过以下代码使用两个 STL priority_queue 来实现：

priority_queue<int> maxHeap; // 大顶堆，用于存储较小的一半数据
priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆，用于存储较大的一半数据
int median = 0;

void insert(int num) {
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }
    // 平衡两个堆的大小
    if (maxHeap.size() - minHeap.size() > 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() - maxHeap.size() > 1) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
    // 计算中位数
    if (maxHeap.size() > minHeap.size()) {
        median = maxHeap.top();
    } else if (maxHeap.size() < minHeap.size()) {
        median = minHeap.top();
    } else {
        median = (maxHeap.top() + minHeap.top()) / 2;
    }
}

int getMedian() {
    return median;
}

以上代码中，我们定义了一个大顶堆 maxHeap 和一个小顶堆 minHeap，用来存储数据流中的数。我们将数据流中的较小数放入大顶堆中，较大数放入小顶堆中，并为了保持两个堆的平衡性而实时调整两个堆的大小和取数方式。最后，我们可以通过 getMedian() 方法获得数据流的中位数。

示例二：最后 K 个数中的最大数

假设有一个数流，且数量较大，我们需要从数流中取出最后 K 个数中的最大值。我们可以通过以下代码使用 STL priority_queue 来实现：

priority_queue<int> maxHeap;

void insert(int num) {
    maxHeap.push(num);
    if (maxHeap.size() > K) {
        maxHeap.pop();
    }
}

int getMax() {
    return maxHeap.top();
}

以上代码中，我们定义了一个大顶堆 maxHeap，每次将数流中的数插入到大顶堆中，并维护堆的大小以保证堆中只有最后 K 个插入的数。最后，我们可以通过 getMax() 方法返回最终的最大值。