c++手写优先级队列

优先级队列是一种数据结构，它提供了按优先级进行元素访问的功能。在C++中，可以使用STL库中的priority_queue类来实现优先级队列。下面是手写优先级队列的示例代码：

#include <iostream>
#include <vector>

using namespace std;

class PriorityQueue {
private:
    vector<int> heap;

    void sink(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int j = 2 * i + 1;
            if (j + 1 < n && heap[j + 1] < heap[j]) {
                j++;
            }
            if (heap[i] <= heap[j]) {
                break;
            }
            swap(heap[i], heap[j]);
            i = j;
        }
    }

    void swim(int i) {
        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
            swap(heap[(i - 1) / 2], heap[i]);
            i = (i - 1) / 2;
        }
    }

public:
    PriorityQueue() {
    }

    void push(int num) {
        heap.push_back(num);
        swim(heap.size() - 1);
    }

    void pop() {
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        sink(0);
    }

    int top() {
        return heap[0];
    }

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

int main() {
    PriorityQueue pq;
    pq.push(5);
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}