题解 | #【模板】堆#

具体堆的知识可进入该网站浏览：

https://blog.csdn.net/qq_34270874/article/details/113091364

#include <iostream>
#include <vector>

using namespace std;

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

    int top() {
        if (heap.empty())
            return -1;
        return heap[0];
    }

    int pop() {
        if (heap.empty())
            return -1;
        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        siftDown(0);
        return maxVal;
    }

private:
    vector<int> heap;

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

    void siftDown(int idx) {
        int size = heap.size();
        while (true) {
            int leftChild = 2 * idx + 1;
            int rightChild = 2 * idx + 2;
            int maxIdx = idx;

            if (leftChild < size && heap[leftChild] > heap[maxIdx])
                maxIdx = leftChild;

            if (rightChild < size && heap[rightChild] > heap[maxIdx])
                maxIdx = rightChild;

            if (maxIdx == idx)
                break;

            swap(heap[idx], heap[maxIdx]);
            idx = maxIdx;
        }
    }
};

int main() {
    int n;
    cin >> n;

    MaxHeap heap;

    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            heap.push(x);
        }
        else if (op == "top") {
            int result = heap.top();
            if (result == -1)
                cout << "empty" << endl;
            else
                cout << result << endl;
        }
        else if (op == "pop") {
            int result = heap.pop();
            if (result == -1)
                cout << "empty" << endl;
            else
                cout << result << endl;
        }
    }

    return 0;
}

siftUp(heap.size() -1)是在将新素插入堆后，调用siftUp函数将新元素向上移动到合适的位置，以维持大根的性质。

siftUp函数的作用是比较当前与其父节点的大小关系，如果当前节点的值大于其父节点值，则交换它们的位置，直到当前节点不再比父节点大或者到达堆顶。

siftUp函数的实现中，传入的参数idx为当前在堆中的索引。首先计算当前节点的父节点的索引位置parent = (idx - 1) / 2，然后进行循环比较交换操作，直到当前节点不再比父节点大或者到达堆顶为止。

具体的比较交换操作如下：

• 如果当前节点的值大于其父节点的值，交换当前节点和父节点的值，将当前节点的索引更新为父节点的索引idx = parent。
• 继续计算新的当前节点的父节点索引parent = (idx - 1) / 2，并进行下一轮的比较交换操作。

通过这一系列的比较和交换操作，新插入的元素会被逐渐向上移动到合适的位置，从而满足大根堆的性质。

在siftUp函数执行完毕后，新元素已经被正确插入并移动到了合适的位置，保持了大根堆的性质。

int maxVal = heap[0];

heap[0] = heap.back();

heap.pop_back();

siftDown(0);

的作用是实现移除堆顶元素，并将堆中最后一个元素放到堆顶位置，然后调用siftDown(0)函数将新的堆顶元素下移到合适的位置，以维持大根堆的性质。

首先，定义一个整数变量maxVal，将堆顶元素的值heap[0]赋给它，即取出堆顶元素的值。

然后，将堆中最后一个元素的值heap.back()赋给堆顶元素heap[0]，即将堆顶元素替换为最后一个元素。

接着，调用pop_back()函数将堆中的最后一个元素删除。

最后，调用siftDown(0)函数，将新的堆顶元素下移到合适的位置，以维持大根堆的性质。

siftDown函数的作用是比较当前节点与其左右子节点的大小关系，如果当前节点的值小于左子节点或右子节点的值，则将当前节点与较大的子节点交换位置，直到当前节点不再比两个子节点小或者到达堆底部。

siftDown函数的实现中，传入的参数idx为当前在堆中的索引。首先计算当前节点的左右子节点的索引位置left = 2 * idx + 1和right = 2 * idx + 2，然后进行循环比较交换操作，直到当前节点不再比两个子节点小或者到达堆底部为止。

具体的比较交换操作如下：

• 如果当前节点的值小于左子节点的值，交换当前节点和左子节点的值，将当前节点的索引更新为左子节点的索引idx = left。
• 如果当前节点的值小于右子节点的值，交换当前节点和右子节点的值，将当前节点的索引更新为右子节点的索引idx = right。
• 继续计算新的当前节点的左右子节点索引left = 2 * idx + 1和right = 2 * idx + 2，并进行下一轮的比较交换操作。

通过这一系列的比较和交换操作，新的堆顶元素会被逐渐向下移动到合适的位置，从而满足大根堆的性质。

在siftDown函数执行完毕后，新的堆顶元素已经被正确移动到了合适的位置，保持了大根堆的性质。

如果以上解析有帮助到你，麻烦给个吧，如果有任何问题也可指出一起交流解决。