C++最大堆

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆可以用來維護一個元素序列的近似最大堆排序，其中堆頂的元素總是序列中的最大元素。

在C++中，可以使用STL中的priority_queue來實現最大堆，因為priority_queue的默認實現就是最大堆。你可以像下面這樣使用它：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> max_heap;

    // 向最大堆中添加元素
    max_heap.push(10);
    max_heap.push(20);
    max_heap.push(30);

    // 輸出堆頂元素（最大元素）
    std::cout << "The maximum element in the heap is: " << max_heap.top() << std::endl;

    // 彈出堆頂元素
    max_heap.pop();

    // 輸出新的最大元素
    std::cout << "The new maximum element in the heap is: " << max_heap.top() << std::endl;

    return 0;
}

在上面的代碼中，我們創建了一個最大堆，然後向其中添加了三個整數。我們使用top()方法來訪問堆頂元素，使用pop()方法來彈出堆頂元素。

如果你想要手動實現最大堆，可以使用以下代碼：

#include <iostream>
#include <vector>

struct MaxHeap {
    std::vector<int> data;

    // 返回節點的左孩子索引
    int left_child_index(int parent_index) {
        return 2 * parent_index + 1;
    }

    // 返回節點的右孩子索引
    int right_child_index(int parent_index) {
        return 2 * parent_index + 2;
    }

    // 返回節點的父節點索引
    int parent_index(int child_index) {
        return (child_index - 1) / 2;
    }

    // 交換兩個節點
    void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    // 調整堆，使得data[index]為最大堆
    void adjust_heap(int index) {
        int left_child_index = this->left_child_index(index);
        int right_child_index = this->right_child_index(index);
        int largest_index = index;

        // 如果左孩子存在且比父節點大，則largest_index指向左孩子
        if (left_child_index < this->data.size() && this->data[left_child_index] > this->data[index])
            largest_index = left_child_index;

        // 如果右孩子存在且比largest_node大，則largest_node指向右孩子
        if (right_child_index < this->data.size() && this->data[right_child_index] > this->data[largest_index])
            largest_index = right_child_index;

        // 如果largest_node不是父節點，交換它們
        if (largest_index != index) {
            this->swap(index, largest_index);
            this->adjust_heap(largest_index);
        }
    }

    // 構建最大堆
    void build_max_heap() {
        for (int i = this->data.size() / 2 - 1; i >= 0; i--)
            this->adjust_heap(i);
    }

    // 插入元素
    void insert(int value) {
        this->data.push_back(value);
        this->build_max_heap();
    }

    // 刪除最大元素
    int extract_max() {
        if (this->data.empty())
            return -1;

        int max_value = this->data[0];
        this->data[0] = this->data.back();
        this->data.pop_back();

        this->adjust_heap(0);

        return max_value;
    }
};

int main() {
    MaxHeap max_heap;

    max_heap.insert(10);
    max_heap.insert(20);
    max_heap.insert(30);

    std::cout << "The maximum element in the heap is: " << max_heap.extract_max() << std::endl;

    return 0;
}

在這個手動實現的例子中，我們定義了一個MaxHeap結構體，它包含一個std::vector來存儲堆中的元素。我們還定義了一些輔助函式來計算孩子節點和父節點的索引，以及交換節點和調整堆。build_max_heap函式用於在向堆中添加新元素後重新構建最大堆，insert函式用於向堆中添加新元素，extract_max函式用於刪除堆頂元素。