在最大堆積樹中刪除最大元素(即堆頂元素)後,通常採用以下步驟來更新堆,以確保其繼續滿足最大堆的性質:
移除堆頂元素:首先移除根節點(即最大元素),通常是將堆中最後一個元素移至根節點位置,以保持完全二叉樹的結構。
下沉調整(Heapify Down):將新的根節點與其子節點比較,如果它小於它的一個或兩個子節點,就將它與最大的子節點交換。重複這個過程,直到當前節點大於它的子節點或者它已經是葉節點。
給定的最大堆積樹為:
46
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
,
3
46,17,23,13,12,6,7,10,15,3
刪除最大元素(46)後,並將最後一個元素(3)移動到根節點的過程如下:
刪除46,將3移至根節點:
3
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
3,17,23,13,12,6,7,10,15
由於3小於其子節點17和23,我們需要進行下沉調整。3與最大的子節點23交換:
23
,
17
,
3
,
13
,
12
,
6
,
7
,
10
,
15
23,17,3,13,12,6,7,10,15
接下來,3還需要與其子節點進行比較。由於3沒有子節點比它大,所以這一步可以省略。
最終更新完的最大堆積樹為:
23
,
17
,
3
,
13
,
12
,
6
,
7
,
10
,
15
23,17,3,13,12,6,7,10,15
這樣,我們就完成了刪除最大堆積樹中的最大元素並進行了必要的調整,以確保結果仍然是一個最大堆。