關於堆（最大堆和最小堆）

我有這樣一個問題，在堆數據結構中，左邊的孩子可能不止是一個正確的孩子在自己的水平？我的意思是考慮這三個數字9,5,8，我想創建一個最大堆數據結構，這樣根就會是9，它是真的，8是它的左邊的孩子，5是它的正確孩子？請幫助我謝謝關於堆（最大堆和最小堆）

來源

2010-06-25 user355002

這沒關係。 max-heap中的節點必須具有較低的子節點，並且min-heap中的節點必須具有較大的子節點。這些是唯一的要求。

來源

2010-06-25 07:11:18

因此，我們如何設置父項的左右子項沒有規則？因爲堆幾乎是完整的二叉樹，我認爲這是二叉樹中的一條規則，讓孩子應該少於正確的孩子！我認爲對於我上面的例子，我應該寫「root：9」和「leftChild：5」和「rightChild：8」，不是嗎？ – user355002 2010-06-25 07:16:23

你通常會建立一個最大堆的方式是從數組的中間開始第一個元素，並通過交換節點遞歸地讓每個節點在樹中向下篩選。這可以在O（n）時間完成。它不是一個二叉搜索樹，所以兄弟節點之間沒有特別的關係，除了它們比它們的父節點更小（或者在min-heap的情況下更大）之外。 – 2010-06-25 07:25:34

aha，如果我們想在這個數據結構中搜索一個關鍵字，我們不需要將它作爲一個二叉搜索樹？ – user355002 2010-06-25 07:45:20

最大堆性能：

Root是最大元素。 O（1）時間來搜索最大元素。
兒童總是比任何子樹的根小。（有左和右孩子之間沒有條件）
最小元件位於簧片元件某處，即爲O（n/2）==Ô （n）需要時間來找到最小元素。

最小堆性能：

根是最小的元素。 O（1）搜索mim元素的時間。
兒童總是比任何子樹的根值。（有左和右孩子之間沒有條件）
最大元件位於簧片元件某處，即爲O（n/2）==Ô （n）需要時間才能找到最大元素。

因此，堆不適合搜索，但它用於排序元素數組，因爲搜索需要線性O（n）時間。

對於搜索，我們總是可以選擇在O（h）時間執行相同操作的二進制搜索樹（BST）。在最好的情況下，如果BS樹是平衡的，它將在O（logn）中進行搜索。

來源

2015-03-31 00:35:25 CODError

關於堆（最大堆和最小堆）

回答

相關問題