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

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

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

插入操作

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

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

刪除最小值

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

C 代碼示例

```cpp

include

using namespace std;

class MinHeap {

public:

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

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

int heap_size; // 當(dāng)前堆中元素的數(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);

}

}

// 減小某個(gè)節(jié)點(diǎn)的值

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);

}

}

// 維護(hù)最小堆的性質(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