搜索堆中的元素

我記得可以使用堆來搜索元素是否在O（logN）時間複雜度中。但突然間我無法瞭解細節。我只能找到getmin刪除添加等。搜索堆中的元素

任何人都可以提示嗎？

2010-03-03 skydoor

您需要搜索堆中的每個元素以確定元素是否在裏面。

儘管（我們假設這裏有一個最大堆），但是可以進行一次優化。如果您到達的節點值低於要搜索的元素的值，則不需要從該節點進一步搜索。但是，即使使用此優化，搜索仍然是O（N）（需要平均檢查N/2個節點）。

2010-03-03 18:08:11

這完全是真的嗎？以下面的堆爲例： '[5,4,1,3]'如果我爲數字3搜索這個堆（以數組的形式），我將按1並根據您的算法在此停止當它實際上不是它堆在一堆時？我在這裏錯過了什麼嗎？ –

通過優化，具有根1的子樹不會被進一步搜索，因爲它不能包含3. 3在另一個子樹中。我同意線性搜索（而不是遞歸）可以給出錯誤的答案。 –

@JamesSanders在所有情況下都是如此，即使是線性搜索。完整的二叉樹的值爲3，左邊的孩子爲4，1與4的高度相同。即使您正在進行線性搜索，優化也表示4> 3，因此您必須至少，比較4的孩子，除了與4高度相同的所有其他元素。 – lee

我認爲你要找的是一個BST（二叉搜索樹）。

2010-03-03 16:29:19 zarkon

+13

如果您已經擁有優先級隊列並且想檢查它是否包含給定元素，那麼這將毫無幫助。 – finnw

回答