【C++篇】排队的艺术：用生活场景讲解优先级队列的实现

熬夜学编程的小王

发布于 2024-11-26 11:19:33

11500

代码可运行

文章被收录于专栏：编程小王编程小王

运行总次数：0

代码可运行

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

深入理解与实现：C++优先级队列的模拟实现

1. 引言

在算法和数据结构中，优先级队列是一种极其重要的工具，用于按优先级而非插入顺序处理数据。在C++中，std::priority_queue提供了强大的内置支持，但了解其原理和实现有助于我们更灵活地应用这一数据结构。本文将带你从基础概念出发，逐步实现一个C++版本的优先级队列，并解析其核心原理。

2. 什么是优先级队列？

优先级队列是特殊的队列数据结构，其中每个元素都带有一个优先级，队列的处理顺序依据优先级而定，而不是入队顺序。常见特性包括：

优先级定义：通常用数值表示，数值越大或越小（取决于实现）表示优先级越高。
操作支持：支持插入、删除优先级最高元素。

2.1 现实生活的比喻

在机场登机时，头等舱乘客拥有更高的优先级，会优先登机；在银行排队时，VIP客户的业务会优先处理。优先级队列以数据结构的方式抽象和实现了这些规则。

3. 优先级队列的实现方式

优先级队列的底层通常基于堆结构（Heap）。堆是一种二叉树，分为最大堆和最小堆：

最大堆：根节点是最大值，每个子节点的值都小于或等于父节点。
最小堆：根节点是最小值，每个子节点的值都大于或等于父节点。

3.1 常见实现方法

基于数组或链表：通过手动排序实现，但效率低下。
基于二叉堆：常见且高效，插入和删除的时间复杂度为O(log n)。
C++ STL中的实现：std::priority_queue利用堆的机制实现优先级队列。

4. 用C++实现优先级队列

接下来，我们将通过代码逐步构建一个优先级队列。

4.1 手动实现优先级队列（基于最大堆）

#include <iostream>
#include <vector>
#include <stdexcept>

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

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

    void siftDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left < heap.size() && heap[left] > heap[largest])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;

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

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

    int pop() {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        int top = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            siftDown(0);
        }
        return top;
    }

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

    int top() const {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        return heap[0];
    }
};

int main() {
    PriorityQueue pq;
    pq.push(10);
    pq.push(20);
    pq.push(5);

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

    return 0;
}

4.2 使用C++标准库实现优先级队列

C++ STL 提供了内置的优先级队列std::priority_queue，使用起来非常方便。

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 默认是最大堆
    std::priority_queue<int> pq;

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

    // 查看和删除堆顶元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 20
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 10

    // 最小堆的实现
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

    std::cout << "Top element of minHeap: " << minHeap.top() << std::endl; // 输出 5
    return 0;
}