二叉堆是一種具有特定屬性的二叉樹，適合存儲在數(shù)組中。在二叉堆中，根節(jié)點的數(shù)值最小，每個節(jié)點的數(shù)值都要小于其子節(jié)點的數(shù)值大小。這種數(shù)據(jù)結(jié)構(gòu)可以用來實現(xiàn)一些常見的操作，如插入、刪除最小值等。下圖是一個二叉

二叉堆是一種具有特定屬性的二叉樹，適合存儲在數(shù)組中。在二叉堆中，根節(jié)點的數(shù)值最小，每個節(jié)點的數(shù)值都要小于其子節(jié)點的數(shù)值大小。這種數(shù)據(jù)結(jié)構(gòu)可以用來實現(xiàn)一些常見的操作，如插入、刪除最小值等。

下圖是一個二叉堆的示例，由于二叉堆是一個完全的二叉樹，所以可以用數(shù)組來表示。根節(jié)點存儲在arr[0]，對任意節(jié)點i，其存儲位置為arr[i]，父節(jié)點的位置為arr[(i-1)/2]，左子節(jié)點的位置為arr[2*i 1]，右子節(jié)點的位置為arr[2*i 2]。

插入操作

插入操作是將一個新的數(shù)值插入到二叉堆中的過程。首先，在二叉堆中根據(jù)完全二叉樹的特性插入一個空白位置，然后將新的數(shù)值插入到空白位置。接著，需要保證父節(jié)點始終比子節(jié)點要小，如果父節(jié)點的大小大于子節(jié)點的大小，就交換父節(jié)點和子節(jié)點的值。這個過程會持續(xù)進行，直到滿足二叉堆的排序特性。

插入一個新數(shù)值的時間復(fù)雜度為O(logN)，其中N是二叉堆中元素的個數(shù)。

刪除最小值

刪除最小值操作是指刪除二叉堆的根節(jié)點。首先獲取根節(jié)點的數(shù)值，然后將二叉堆的最后一個元素放到根節(jié)點的位置，然后讓該元素層層下降到滿足二叉堆排序特性為止。

C 代碼示例

```cpp

include

using namespace std;

class MinHeap {

public:

int *arr; // 指向堆中元素的數(shù)組

int capacity; // 數(shù)組的容量

int heap_size; // 當前堆中元素的數(shù)量

public:

MinHeap(int cap);

int parent(int i) { return (i-1)/2; }

int left(int i) { return 2*i 1; }

int right(int i) { return 2*i 2; }

void insertValue(int k);

int getMin() { return arr[0]; }

void decreaseKey(int i, int new_key);

void minHeapify(int i);

int extractMin();

void deleteKey(int i);

};

// 初始化

MinHeap::MinHeap(int cap) {

capacity cap;

heap_size 0;

arr new int[cap];

}

// 插入操作

void MinHeap::insertValue(int k) {

if (heap_size capacity) {

cout << "無法插入數(shù)值" << endl;

return;

}

heap_size ;

int i heap_size - 1;

arr[i] k;

while (i ! 0 arr[parent(i)] > arr[i]) {

swap(arr[i], arr[parent(i)]);

i parent(i);

}

}

// 減小某個節(jié)點的值

void MinHeap::decreaseKey(int i, int new_key) {

arr[i] new_key;

while (i ! 0 arr[parent(i)] > arr[i]) {

swap(arr[parent(i)], arr[i]);

i parent(i);

}

}

// 維護最小堆的性質(zhì)

void MinHeap::minHeapify(int i) {

int l left(i);

int r right(i);

int smallest i;

if (l < heap_size arr[l] < arr[i])

smallest l;

if (r < heap_size arr[r] < arr[smallest])

smallest r;

if (smallest ! i) {

swap(arr[i], arr[smallest