數據結構和算法教學
環境設置
數據結構算法基礎
數據結構漸近分析
數據結構基本概念
數組
哈希表
哈希表實例程序(C語言)
鏈表
鏈表實例程序(C語言)
雙向鏈表
循環鏈表
循環鏈表實例程序(C語言)
堆棧
堆棧實例代碼(C語言)
表達式分析
隊列
隊列實例代碼(C語言)
隊列優先級
線性搜索(查找)
線性搜索實例程序(C語言)
二進制搜索(查找)
二進制搜索/查找程序(C語言)
冒泡排序算法
冒泡排序算法實例程序(C語言)
插入排序
選擇排序
選擇排序實例程序(C語言)
合併排序算法
合併排序算法實例程序(C語言)
希爾排序
希爾排序實例程序(C程序)
快速排序
快速排序實例程序(C語言)
圖數據結構
深度優先遍歷
廣度優先遍歷
樹(二叉樹)
樹遍歷
二叉搜索樹
堆
遞歸基礎知識
堆
堆是平衡二叉樹數據結構,其中根節點鍵與它的子相比並設置相應在一種特殊情況。如果α有子節點β那麼 -
key(α) ≥ key(β)
作爲父的值大於這個子,這個屬性會產生最大堆。基於該標準堆可以有兩種類型 -
For Input → 35 33 42 10 14 19 27 44 26 31
- 最小堆 − 其中根節點的值小於或等於任一其子點。
- 最大堆 − 其中根節點的值大於或等於任一其子節點。
兩個樹都使用相同的輸入及到達順序構成。
最大堆構造算法
我們將用同樣的例子來說明如何創建最大堆。程序創建最大堆與最小堆是類似,但使用最小值代替最大值。
我們將通過一次插入一個元素以導出最大堆算法。在任何時間點,堆必須保持其性能。 當在插入時,假設插入在堆字段在樹中的節點。
Step 1 − 在堆的末尾創建新節點
Step 2 − 分配節點的新值
Step 3 − 比較其父與這個孩子節點的值
Step 4 − 如果父值小於子,那麼交換它們
Step 5 − 重複步驟3和4,直到堆屬性保存
注 − 在最小堆構造算法,預計父節點的值要小於子節點。
我們先看一張卡通插圖來了解最大堆構建。拿我們之前用的相同輸入樣本。
最大堆刪除算法
讓我們推導一個算法的最大堆刪除。刪除最大(小)堆總是發生在根部去除最大(或最小)值。
Step 1 − 刪除
Step 2 − 分配節點的新值
Step 3 − 比較其父與這個孩子節點的值
Step 4 − 如果父值小於子,那麼交換它們
Step 5 − 重複步驟3和4,直到堆屬性保存