C++如何实现优先队列

优先队列（Priority Queue）是一种特殊的队列，其中的元素按照优先级顺序出队，而不是按照先进先出的顺序。优先队列通常用于任务调度、事件模拟等场景。在C++中，优先队列可以通过标准库中的std::priority_queue来实现，也可以手动实现一个优先队列。

使用std::priority_queue

C++标准库提供了std::priority_queue模板类，它位于<queue>头文件中。std::priority_queue默认是一个最大堆，即优先级最高的元素（最大值）位于队列的顶部。

基本用法

#include <iostream>
#include <queue>

int main() {
    // 创建一个最大堆优先队列
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 访问顶部元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 30

    // 删除顶部元素
    pq.pop();

    // 再次访问顶部元素
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20

    return 0;
}

自定义比较函数

如果你想实现一个最小堆，可以通过自定义比较函数来实现。std::priority_queue的第三个模板参数可以指定比较函数。

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于 std::greater

int main() {
    // 创建一个最小堆优先队列
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 访问顶部元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 10

    // 删除顶部元素
    pq.pop();

    // 再次访问顶部元素
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20

    return 0;
}

手动实现优先队列

虽然std::priority_queue非常方便，但有时我们可能需要手动实现一个优先队列，以便更好地理解其工作原理或满足特定需求。优先队列通常基于堆（Heap）数据结构来实现。

基于数组的堆实现

下面是一个简单的基于数组的最大堆实现：

#include <iostream>
#include <vector>

class MaxHeap {
private:
    std::vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] > heap[parent]) {
                std::swap(heap[index], heap[parent]);
                index = parent;
            } else {
                break;
            }
        }
    }

    void heapifyDown(int index) {
        int size = heap.size();
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largest = index;

            if (leftChild < size && heap[leftChild] > heap[largest]) {
                largest = leftChild;
            }
            if (rightChild < size && heap[rightChild] > heap[largest]) {
                largest = rightChild;
            }

            if (largest != index) {
                std::swap(heap[index], heap[largest]);
                index = largest;
            } else {
                break;
            }
        }
    }

public:
    void push(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    void pop() {
        if (heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    int top() {
        if (heap.empty()) throw std::out_of_range("Heap is empty");
        return heap[0];
    }

    bool empty() {
        return heap.empty();
    }
};

int main() {
    MaxHeap pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "Top element: " << pq.top() << std::endl; // 输出 30

    pq.pop();

    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20

    return 0;
}

解释

• heapifyUp：当插入新元素时，将其与父节点比较，如果大于父节点则交换，直到满足堆的性质。
• heapifyDown：当删除顶部元素时，将最后一个元素移到顶部，然后将其与子节点比较，如果小于子节点则交换，直到满足堆的性质。

总结

C++中的优先队列可以通过std::priority_queue轻松实现，也可以通过手动实现堆结构来满足特定需求。优先队列在算法和数据结构中有着广泛的应用，理解其实现原理对于编写高效的代码非常重要。