最小堆的建立

最小堆（Min Heap）是一種特殊的完全二叉樹，其中每個節點的值都不大於其父節點的值。最小堆可以用來實現優先佇列，其中堆頂總是當前序列中的最小元素。最小堆的建立通常涉及以下幾個步驟：

1. 初始化堆：首先，你需要一個數組來存儲堆中的元素。數組的下標從0開始，數組的容量需要足夠大以存儲所有的元素。

2. 堆化：將數組中的元素構建成最小堆的過程稱為堆化。這個過程通常從數組的最後一個非葉子節點開始，向上調整每個節點，直到根節點。

3. 調整堆：當你向堆中添加新的元素或從堆中刪除元素時，堆的結構會被破壞，這時你需要調整堆，使其重新成為最小堆。

下面是一個簡單的C++代碼示例，用於建立一個最小堆：

#include <iostream>
#include <vector>

// 最小堆節點
struct MinHeapNode {
    int data;
    int left;
    int right;
    int parent;
};

// 最小堆
class MinHeap {
private:
    int capacity;
    int size;
    MinHeapNode* heap;

public:
    MinHeap(int capacity) : capacity(capacity), size(0), heap(new MinHeapNode[capacity]) {
        // 初始化堆
        for (int i = 0; i < capacity; i++) {
            heap[i].data = 0;
            heap[i].left = 2*i + 1;
            heap[i].right = 2*i + 2;
            heap[i].parent = (i-1) / 2;
        }
    }

    // 調整堆
    void adjustHeap(int i) {
        // 交換當前節點和其父節點
        if (heap[i].parent >= 0 && heap[heap[i].parent].data > heap[i].data) {
            std::swap(heap[i].data, heap[heap[i].parent].data);
            adjustHeap(heap[i].parent);
        }
    }

    // 堆化
    void heapify() {
        // 從最後一個非葉子節點開始堆化
        for (int i = (capacity - 2) / 2; i >= 0; i--) {
            adjustHeap(i);
        }
    }

    // 獲取堆頂元素
    int top() {
        return heap[0].data;
    }

    // 刪除堆頂元素
    void pop() {
        // 將最後一個元素移動到堆頂
        heap[0] = heap[--size];
        heap[0].parent = -1;
        adjustHeap(0);
    }

    // 向堆中添加元素
    void push(int data) {
        heap[size++] = {data, -1, -1, -1};
        adjustHeap(size - 1);
    }

    // 獲取堆的大小
    int size() {
        return size;
    }
};

int main() {
    MinHeap minHeap(10);
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(7);
    minHeap.push(3);
    minHeap.heapify();

    std::cout << "最小堆頂元素: " << minHeap.top() << std::endl;
    minHeap.pop();
    std::cout << "刪除堆頂元素後的最小堆頂元素: " << minHeap.top() << std::endl;

    return 0;
}

這段代碼定義了一個最小堆類，其中包含了一些基本的操作，如添加元素、刪除堆頂元素、獲取堆頂元素和堆的大小。在main函式中，我們創建了一個容量為10的最小堆，並向其中添加了一些元素，然後調用heapify方法將堆結構調整為最小堆。最後，我們列印了堆頂元素，並刪除堆頂元素後再次列印堆頂元素。