在最大堆中搜索第7大元素？

所以我和我的朋友在這個問題上沒有看到對方的眼睛。它要求在n個元素的最大堆中搜索第7大元素的時間複雜度？在最大堆中搜索第7大元素？

我認爲它應該是O（n），她認爲它應該是O（1）。我的邏輯是，假設n是7，那麼第7個最大的元素將是堆中的最後一個元素，所以如果我們考慮最壞的情況，它應該是O（n）。然而，她表示，因爲這是一個最大的堆，所以找到第七大元素應該花時間。但在O（1）時間內，即使使用她的邏輯，甚至可以找到第50個最大元素或第100個最大元素。另外，我們遇到這個問題的書說解決方案將是O（logn）。

有人可以告訴我哪個解決方案是正確的嗎？

來源

2014-02-06 bigbong

有一個O（1）解決方案。我們假設堆被重新塑造成一棵樹，最大元素是一個根。與具有第7個最大元素的節點和根之間的距離小於或等於6.距離根< = 6的節點數永遠不會大於1 + 2 + 4 + 8 + 16 +32 + 64 = 127.這是一個常數。他們可以在不斷的時間裏遍歷。

來源

2014-02-06 11:42:54 kraskevich

要說有一個O（1）解決方案就是說，不管k或n的值如何，你都可以在恆定時間內在大小爲n的堆中找到第k個最大的元素。你提出的是一個時間複雜度爲O（k）的解決方案。 –

如果k是一個常數，那麼2^k是O（1）。 – kraskevich

這就是我上面提到的......通過你的邏輯，即使找到第50個最大的元素也需要不變的時間嗎？ – bigbong

的簡單的算法找到了第七大元件在最大堆是

repeat 6 times: 
    del-max(heap) 
return max(heap)

第一環路執行一個恆定數量del-max操作，每次取O（LG Ñ）時間。 max操作需要一段時間。操作占主導地位，導致總計O（複雜度）。我並不是說這是最佳的。

來源

2014-02-06 10:44:35

我不是很忙，但是你不是指'max'而不是'min'嗎？這聽起來不合邏輯，刪除六個最小的元素後，新的最小值是原來的第7 * - 最大* ... –

@SillyFreak固定，謝謝。 –

實際上它是O（k log n），其中'k'是項目編號。不是O（log n）。 –

有一種O（k）算法用於選擇大小爲n的堆中的第k個元素，其中n >> k。 Greg Frederickson的An Optimal Algorithm for Selection in a Min-Heap。

您可以從該頁面下載PDF（鏈接在左上方）。

所以答案是你，你的朋友和你正在閱讀的書都是錯的。

來源

2014-02-06 15:08:53

但是由於k = 7在這裏，我們將會有一個O（7）的複雜性，所以這不會僅僅將問題簡化爲O（1）？ – bigbong

是的。如果你保持k不變，那麼複雜度是恆定的。 –

對..把它。謝謝。 – bigbong

在最大堆中搜索第7大元素？

回答

相關問題