我不明白為什么完全二叉樹最適合實作堆？為什么我們不能使用完整的二叉樹？為什么完全二叉樹最適合堆實作？
uj5u.com熱心網友回復：
堆的完整二叉樹？
完整的二叉樹不一定是平衡的。例如，這是一個完整的二叉樹：
1
/ \
2 3
/ \
4 5
/ \
6 7
/ \
8 9
/ \
10 11
通常，任何右孩子也是葉子的完整二??叉樹的高度為 O(??)，更準確地說，是 (???1)/2。這對于堆來說是有問題的，因為它依賴于樹的平衡來將其插入/洗掉操作保持在 O(log??) 的時間復雜度內。
其次，完整的二叉樹總是有奇數個節點（除非它們是空的）。這已經使它們變得不切實際，因為顯然堆也應該能夠具有均勻的大小。
其他選擇
但是，二叉堆不一定是完整的二叉樹。僅當它們的實作是眾所周知的基于陣列的實作時才需要這樣做。但是也可以用 AVL 樹實作二叉堆，它不一定是一棵完整的二叉樹，但它仍然保持樹的平衡，并且對于堆操作具有相同的時間復雜度。但是由于指標管理的開銷大于使用陣列中的索引，因此陣串列示會導致更快的操作。
為什么要完成？
當實作是基于陣列而不是顯式的節點指標表示時，選擇完整的二叉樹就會發揮作用。當您使用level-order中的值填充陣列并且不允許陣列中存在間隙（未使用的插槽）時，則樹是完整的。盡管您可以想象一個允許間隙的陣列，但這將是一個較差的選擇，因為它浪費空間，并且沒有任何收益來補償它。
uj5u.com熱心網友回復：
首先，如果沒有緊密包裝，就不可能創建堆結構。陣列中的每一項在二叉樹中都有一個位置，這個位置來自于陣列索引。
此外，它還具有以下幾個優點：
堆的某些操作具有樹的高度
O(lgn)在哪里的時間復雜度n，將樹的高度保持在最低限度可以讓我們將這些操作所需的時間保持在最低限度。完整二叉樹的所有項都以連續方式存盤在陣列中，因此通過將堆保持為完整二叉樹，可以進行隨機訪問
完整性確保了在洗掉元素時有一種定義明確且有效的方法來確定新的根，不使用完整的結構將意味著失去這種優勢（這就是為什么你應該首先使用堆）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/479288.html