最小堆c++

最小堆（Min Heap）是一種特殊的完全二叉樹，也稱為優先佇列，其中每個節點的值都不大於其父節點的值。最小堆可以用於實現優先佇列，其中堆頂總是包含最小元素。最小堆可以支持以下操作：

1. 插入（Insert）：向堆中添加一個新元素。
2. 刪除最小元素（ExtractMin）：移除並返回堆頂的最小元素，然後通過調整堆結構來保持其性質。
3. 查找最小元素（FindMin）：返回堆頂的最小元素，但不移除它。
4. 調整堆（Heapify）：在堆中插入或刪除一個元素後，調整堆的結構以保持其性質。

下面是一個簡單的C++最小堆實現，使用數組來存儲堆中的元素：

#include <iostream>
#include <vector>

template <typename T>
class MinHeap {
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 adjust_heap(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(i, largest);
            adjust_heap(largest);
        }
    }

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

    int size() const {
        return size;
    }

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

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

    T extract_min() {
        if (empty())
            throw std::runtime_error("Heap is empty");
        T min_element = data[0];
        data[0] = data[--size];
        if (size > 0) {
            int i = 0;
            while (2 * i < size) {
                int j = 2 * i;
                if (j < size - 1 && data[j + 1] < data[j])
                    j++;
                if (data[i] > data[j]) {
                    swap(i, j);
                    i = j;
                } else {
                    break;
                }
            }
        }
        return min_element;
    }

    T find_min() const {
        if (empty())
            throw std::runtime_error("Heap is empty");
        return data[0];
    }
};

int main() {
    MinHeap<int> min_heap;

    min_heap.insert(10);
    min_heap.insert(3);
    min_heap.insert(7);
    min_heap.insert(5);
    min_heap.insert(9);

    std::cout << "Extract min: " << min_heap.extract_min() << std::endl;
    std::cout << "Extract min: " << min_heap.extract_min() << std::endl;
    std::cout << "Extract min: " << min_heap.extract_min() << std::endl;

    return 0;
}

這個最小堆類定義了一個私有成員data，它是一個存儲堆中元素的向量。size是堆中元素的數量。swap函式用於交換兩個元素的位置，adjust_heap函式用於在插入新元素後調整堆的結構。insert函式用於向堆中插入新元素，extract_min函式用於刪除最小元素，find_min函式用於查找最小元素但不刪除它。

在main函式中，我們創建了一個最小堆，並向其中插入了一些元素。然後我們調用extract_min函式來刪除並列印最小元素。

請注意，這個實現使用了數組來存儲堆中的元素，因此它的大小是有限的，並且當堆滿時需要重新分配記憶體。在實際套用中，可能需要使用其他數據結構（如鍊表或平衡二叉樹）來避免這種限制。