优先队列简易实现——C++

tips: 在头文件（类的定义）中设参数默认值，在cpp文件（类的实现）中只使用参数，不设默认值（否则会报告重赋默认值错误）。在最终使用成员函数时即为带默认参数的

(好久没写C++类了，成员函数都有点写不来了。。。(ノへ￣、) )

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


class priority_queue {
private:
    int n;
    vector<int> heap;
    bool isMaxHeap;
public:
    priority_queue(bool _isMaxHeap = true);
    void downAdjust(int low, int high);
    void upAdjust(int low, int high);
    void push(int x);
    void pop();
    int top();
    int size();
};

int main() {
    int n;
    int x, res = 0;
    bool isMaxHeap = false;
    priority_queue q(isMaxHeap);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        q.push(x);
    }
    while (q.size() >= 2) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        int c = a + b;
        res += c;
        q.push(c);
    }
    cout << res;
    // cout << q.size() << endl;
    // while (q.size() > 0) {
    //     cout << q.top() << " ";
    //     q.pop();
    // }
    return 0;
}


priority_queue::priority_queue(bool _isMaxHeap) {
    n = 0;
    isMaxHeap = _isMaxHeap;
    heap.emplace_back(0); // let the index of heap from 1 to n, not 0 to n - 1.
}

void priority_queue::downAdjust(int low, int high) {
    int i = low;
    int j = 2 * i;
    if (isMaxHeap) { // maxHeap
        while (j <= high) {
            if (j + 1 <= high && heap[j + 1] > heap[j]) j = j + 1;
            if (heap[j] > heap[i]) {
                swap(heap[i], heap[j]);
                i = j;
                j = 2 * i;
            } else break;
        }
    } else { // minHeap
        while (j <= high) {
            if (j + 1 <= high && heap[j + 1] < heap[j]) j = j + 1;
            if (heap[j] < heap[i]) {
                swap(heap[i], heap[j]);
                i = j;
                j = 2 * i;
            } else break;
        }
    }
}

void priority_queue::upAdjust(int low, int high) {
    int i = high;
    int j = i / 2;
    if (isMaxHeap) { // maxHeap
        while (j >= low) {
            if (heap[j] < heap[i]) {
                swap(heap[i], heap[j]);
                i = j;
                j = i / 2;
            } else break;
        }
    } else { // minHeap
        while (j >= low) {
            if (heap[j] > heap[i]) {
                swap(heap[i], heap[j]);
                i = j;
                j = i / 2;
            } else break;
        }
    }
}

void priority_queue::push(int x) {
    heap.emplace_back(x);
    ++n;
    upAdjust(1, n);
}

void priority_queue::pop() {
    heap[1] = heap.back();
    heap.pop_back();
    --n;
    downAdjust(1, n);
}

int priority_queue::top() {
    return heap[1];
}

int priority_queue::size() {
    return n;
}