二進制堆中最小的元素？

-2

爲什麼在二進制堆中查找最小事件需要O（log V）時間？（其中V是元素的數量）二進制堆中最小的元素？

Quicksort分而治之算法花費O（V）時間來查找最小的元素。由於在二進制堆中查找最小元素與Quicksort幾乎相同（在每一步中都將問題的大小除以2，問題的數量保持不變），爲什麼他們有不同的時間？

爲什麼找到使用Quicksort的最小元素並找到二進制堆中最小的元素需要不同的時間量？

2012-06-21 fdh

修改您的假設。 Quicksort沒有找到最小的元素（相反，它排序，這是一個更大的和完全不同的問題），並且不會在O（V）中運行（在最壞的情況下，我假設你沒有得到更具體的結果）。二進制堆給你O（1）中最小的元素，假設你只是檢索它並不刪除它（這需要重新排序以維護堆屬性，並且這是需要O（log V）時間的那個步驟）。 – delnan

@delnan 1）二進制堆如何取O（n）？它不需要首先找到元素嗎？二進制堆沒有排序 - 父母只是比孩子大。 2）不會排序一組數字允許找到O（1）時間中的最小元素？因爲如果一個集合被排序，最小的數字就是最後一個數字 – fdh

（1）我假設一個最小堆，這是常見的，並且對於這個用例來說效率更高。唯一的區別是* *小*元素放在最上面（即換掉>換成<）。（2）是的，你可以很容易地得到最小值，但這不是Quicksort（相反，它是一個獨特的算法，恰好利用任何排序算法），它仍然不是O（V）*最壞情況* 。即使你擊中O（V）平均值/最佳情況，你也可以找到最小值。通過'minx = xs [0]在O（V）中更簡單（並且方法更低）。 for x in xs：minx = min（minx，x）'。 – delnan

任何min-heap（不一定是二進制）會給你O(1)時間中的最小元素。這是因爲最小的元素是堆的根（滿足堆屬性）。

我認爲這裏的問題是你混淆了你的數據結構。在未排序列表任何算法至少需要O(N)時間，其中N是元素的數量。

如果您的數據已經存儲在堆結構中，則可以在O(1)時間內提取最小值。但值得注意的是，從未排序的列表中首先構建堆將花費O(N)時間。

如果你有一個排序列表，那麼你可以使用二進制搜索找到最小的O(log N)時間。但是，排序至少需要O(N)。

來源

2012-06-21 19:58:28 tskuzzy

如何從未排序的列表構建一個二進制堆取O（n）？用最少的O（n log n）時間來對一組數字進行排序並使用Mergesort等算法？ – fdh

你正在談論兩件不同的事情。構建二進制堆與排序不同。有關算法，請參閱http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。 – tskuzzy

如果列表已排序，則不應將最小值設爲O（1），因爲它只是第一個（或最後一個，取決於排序順序）項目？ – delnan

假設您正在嘗試查找最大堆中的最小元素，如您所說，它將花費O（V）時間，而不是O（log V）時間。這個問題在每一步都沒有分成兩半。因爲一旦你建立它比根部小，最小的元素可以在任何2子樹中。因此，您需要遍歷兩個子樹以找到最小元素。

來源

2012-06-21 19:59:30

假設您正在討論基於樞軸的選擇算法，它與quicksort非常相似，在兩種情況下找到最小值都有根本的不同。我的意思是，基於快速排序的選擇算法選擇一個數據透視表並對您的元素進行分區，然後您知道剩餘的數據段中您正在查找的數字是哪一個。二進制堆沒有類似的屬性。堆的特殊性質是每個節點都小於它的父節點（假設我們正在討論最大堆）。就像其中一個其他答案所述，這限制了O（log（V））的可行候選數量，因爲這是二進制堆中有多少葉子。但是，（據我所知），您必須保留葉子列表，或者您的堆必須表示爲數組，以便從中獲得時間複雜性優勢。如果你的堆是作爲一組鏈接節點存儲的，它只有一個指向第一個元素的指針，在最壞的情況下，你必須搜索它的所有子節點才能找到最小值，因爲這是唯一的方法，你甚至可以看到樹葉。我知道這個問題已經有很多答案了，其中大部分都是正確的，但我希望這可以澄清一些事情。另外，爲了清楚起見，實際的快速排序算法（如果是隨機的）以分期O（nlogn）時間運行。在排序數組中找到最少的元素是O（1）。

來源

2012-06-21 22:32:58

二進制堆中最小的元素？

回答

相關問題