最大堆c++

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆可以用來構建優先佇列，其中堆頂的元素總是佇列中最大的元素。

在C++中，可以使用模板類來實現最大堆。以下是一個簡單的最大堆實現示例：

#include <iostream>
#include <vector>

template <typename T>
class MaxHeap {
private:
    std::vector<T> data;
    int size;

    void swap(int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    void adjustHeap(int i) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int largest = i;

        if (l < size && data[l] > data[largest])
            largest = l;
        if (r < size && data[r] > data[largest])
            largest = r;
        if (largest != i) {
            swap(largest, i);
            adjustHeap(largest);
        }
    }

public:
    MaxHeap() : size(0) {}

    void push(T item) {
        data.push_back(item);
        size++;
        int i = size - 1;
        while (i > 0 && data[i / 2] < data[i]) {
            swap(i, i / 2);
            i /= 2;
        }
    }

    T pop() {
        if (size == 0)
            return T();
        T ret = data[0];
        data[0] = data[--size];
        if (size > 0) {
            int i = 0;
            while (i * 2 + 1 < size) {
                int j = i * 2 + 1;
                if (j < size - 1 && data[j + 1] > data[j])
                    j++;
                if (data[i] < data[j]) {
                    swap(i, j);
                    i = j;
                } else {
                    break;
                }
            }
        }
        return ret;
    }

    int size() const {
        return size;
    }

    bool empty() const {
        return size == 0;
    }
};

int main() {
    MaxHeap<int> heap;
    heap.push(10);
    heap.push(1);
    heap.push(5);
    heap.push(7);
    heap.push(2);

    while (!heap.empty()) {
        std::cout << heap.pop() << " ";
    }
    std::cout << std::endl;
    return 0;
}

在這個例子中，MaxHeap 類使用了一個 std::vector 來存儲數據，並提供了一些操作堆的方法，如 push、pop、size 和 empty。adjustHeap 函式用於在插入新元素後調整堆的形狀，swap 函式用於交換兩個元素的位置。

在 push 函式中，新元素被添加到堆的末尾，然後通過一個循環向上調整堆的形狀，直到新元素成為其父節點的最大子節點。在 pop 函式中，堆頂元素被彈出，然後通過一個循環向下調整堆的形狀，直到堆頂元素成為其子節點的最大值。

這個最大堆的實現是高效的，因為它使用了二叉堆的數據結構，插入和刪除最大元素的時間複雜度都是 O(log n)。