C++如何實現優先隊列

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非常方便，但有時我們可能需要手動實現一個優先隊列，以便更好地理解其工作原理或滿足特定需求。優先隊列通?；诙眩℉eap）數據結構來實現。

基于數組的堆實現

下面是一個簡單的基于數組的最大堆實現：

#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輕松實現，也可以通過手動實現堆結構來滿足特定需求。優先隊列在算法和數據結構中有著廣泛的應用，理解其實現原理對于編寫高效的代碼非常重要。