本文介紹二叉堆，二叉堆就是通常我們所說的數據結構"堆"中的一種。和以往一樣，本文會先對二叉堆的理論知識進行簡單介紹，然后給出C語言的實現。后續再分別給出C++和Java版本的實現；實現的語言雖不同，但是原理如出一轍，選擇其中之一進行了解即可。若文章有錯誤或不足的地方，請不吝指出！

堆和二叉堆的介紹

1. 堆的定義

堆(heap)，這里所說的堆是數據結構中的堆，而不是內存模型中的堆。堆通常是一個可以被看做一棵樹，它滿足下列性質：

[性質一] 堆中某個節點的值總是不大于或不小于其父節點的值；

[性質二] 堆總是一棵完全樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、左傾堆、斜堆、斐波那契堆等等。

2. 二叉堆的定義

二叉堆是完全二元樹或者是近似完全二元樹，它分為兩種：最大堆和最小堆。示意圖如下：

最大堆：父結點的鍵值總是大于或等于任何一個子節點的鍵值；

最小堆：父結點的鍵值總是小于或等于任何一個子節點的鍵值。

二叉堆一般都通過"數組"來實現。數組實現的二叉堆，父節點和子節點的位置存在一定的關系。有時候，我們將"二叉堆的第一個元素"放在數組索引0的位置，有時候放在1的位置。當然，它們的本質一樣(都是二叉堆)，知識實現上稍微有一丁點區別。

假設"第一個元素"在數組中的索引為 0 的話，則父節點和子節點的位置關系如下：

(01) 索引為i的左孩子的索引是 (2*i+1);

(02) 索引為i的左孩子的索引是 (2*i+2);

(03) 索引為i的父結點的索引是 floor((i-1)/2)。

假設"第一個元素"在數組中的索引為 1 的話，則父節點和子節點的位置關系如下：

(01) 索引為i的左孩子的索引是 (2*i);

(02) 索引為i的左孩子的索引是 (2*i+1);

(03) 索引為i的父結點的索引是 floor(i/2)。

注意：本文二叉堆的實現統統都是采用"二叉堆第一個元素在數組索引為0"的方式！

二叉堆的圖文解析

在前面，我們已經了解到："最大堆"和"最小堆"是對稱關系。這也意味著，了解其中之一即可。本文是以"最大堆"來進行介紹的。

二叉堆的核心是"添加節點"和"刪除節點"，理解這兩個算法，二叉堆也就基本掌握了。下面對它們進行介紹。

1. 添加

假設在最大堆[90,80,70,60,40,30,20,10,50]種添加85，需要執行的步驟如下：

如上圖所示，當向最大堆中添加數據時：先將數據加入到最大堆的最后，然后盡可能把這個元素往上挪，直到挪不動為止！

將85添加到[90,80,70,60,40,30,20,10,50]中后，最大堆變成了[90,85,70,60,80,30,20,10,50,40]。

最大堆的插入代碼

/*

* 將data插入到二叉堆中

*

* 返回值：

* 0，表示成功

* -1，表示失敗

*/

int maxheap_insert(int data)

{

// 如果"堆"已滿，則返回

if(m_size == m_capacity)

return -1;

m_heap[m_size] = data; // 將"數組"插在表尾

maxheap_filterup(m_size); // 向上調整堆

m_size++; // 堆的實際容量+1

return 0;

}

maxheap_insert(data)的作用：將數據data添加到最大堆中。當堆已滿的時候，添加失敗；否則data添加到最大堆的末尾。然后通過上調算法重新調整數組，使之重新成為最大堆。

2. 刪除

假設從最大堆[90,85,70,60,80,30,20,10,50,40]中刪除90，需要執行的步驟如下：

從[90,85,70,60,80,30,20,10,50,40]刪除90之后，最大堆變成了[85,80,70,60,40,30,20,10,50]。

如上圖所示，當從最大堆中刪除數據時：先刪除該數據，然后用最大堆中最后一個的元素插入這個空位；接著，把這個“空位”盡量往上挪，直到剩余的數據變成一個最大堆。

注意：考慮從最大堆[90,85,70,60,80,30,20,10,50,40]中刪除70，執行的步驟不能單純的用它的字節點來替換；而必須考慮到"替換后的樹仍然要是最大堆"！

最大堆的刪除代碼

/*

* 刪除最大堆中的data

*

* 返回值：

* 0，成功

* -1，失敗

*/

int maxheap_remove(int data)

{

int index;

// 如果"堆"已空，則返回-1

if(m_size == 0)

return -1;

// 獲取data在數組中的索引

index = get_index(data);

if (index==-1)

return -1;

m_heap[index] = m_heap[--m_size]; // 用最后元素填補

maxheap_filterdown(index, m_size-1); // 從index位置開始自上向下調整為最大堆

return 0;

}

maxheap_remove(data)的作用：從最大堆中刪除數據data。

當堆已經為空的時候，刪除失敗；否則查處data在最大堆數組中的位置。找到之后，先用最后的元素來替換被刪除元素；然后通過下調算法重新調整數組，使之重新成為最大堆。

二叉堆的實現源碼和測試包括

二叉堆的源碼包含了"最大堆"和"最小堆"。

PS. 二叉堆是"堆排序"的理論基石。后面的算法中會講解到"堆排序"，理解了"二叉堆"之后，"堆排序"就很簡單了。

總結

以上是生活随笔為你收集整理的大根堆的删除c语言,二叉堆(一)之 C语言详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。