特殊的minHeap，如何打印O（n）中的所有n個元素？

Speical minHeap是一個minHeap，每個級別從左到右排序。如何在最差情況下按O(n)的順序打印所有n元素？特殊的minHeap，如何打印O（n）中的所有n個元素？

minHeap是由二進制堆實現的，其中樹是一個完整的二叉樹（見圖）。

這裏是一個特殊的minHeap的例子：

所以結果應該是：從作業[1,3,4,5,8,10,17,18,20,22,25,30]

問題。

來源

2016-03-08 user3781974

您可能想要說明您正在使用什麼類型的數據結構來存儲堆。 – ilim

顯然不是** MergeSort **，因爲** MergeSort **需要'O（nlogn）' –

這是一個練習/作業嗎？ – WhatsUp

如果n是一個獨立於堆大小的參數，那麼在標準的基於比較的模型下，這是不可能的。你將需要額外的限制，比如你已經提到的先前存在的順序，或者堆的所有元素都是在一個足夠低的範圍內的整數。

假設您有一堆高度爲k，其中左邊兒童的根和其鏈的值爲1,2,3，... k。我們可以按照任意順序爲這些節點的k-1個右側子節點賦值> k，而不違反「特殊minheap」條件，然後分配大於那些值的值來填充堆的其餘部分。在該堆中打印頂部的2k-1值需要對可能以任何順序排列的k-1值進行排序，這是通過比較小於O(k*log(k))時間無法完成的。

如果n應該是所述堆的大小，這是簡單的。堆不變是不必要的;它只是重要的圖層排序。 mergesort合併第一層和第二層，然後將每個連續的層合併到已經合併的結果中，將耗時O（n）。第k個合併將來自下一層的2^k-1個已經合併的元素與< = 2^k個元素合併，花費O（2^k）時間。有O（log（n））合併，並且從k = 1到k = log（n）求和O（2^k）給出O（n）。

來源

2016-03-08 19:10:23 user2357112

這是我想到的論點，但有時'minHeap'的定義要求它是一個完整的二叉樹（如示例中所示）。所以我仍然不確定。 – WhatsUp

@WhatsUp：這個參數使用了一個完整的二叉樹，所以我不確定你看到了什麼問題。 – user2357112

完整的堆將有'2^k'節點，所以這個問題需要在'O（2^k）'時間內打印出所有的節點。這與在'O（k）'時間內打印出第一個'2k - 1'的值稍有不同。 – WhatsUp

堆的每個級別按升序排列。有log（n）級別。

我們可以進行水平合併，即O（n log k）。 k在這種情況下是等級數或log（n），所以我們知道可以在O（n * log（log n））中執行此操作。

這些關卡中有1,2,4,8,16等節點。第一次合併操作刪除第一級，因此我們合併堆中的項目數量變爲k-1。在最糟糕的情況下，在刪除了一半節點後，合併堆爲k-2等。

我沒有數學手頭，但我懷疑解決方案涉及顯示擴展系列（即跟蹤合併堆大小，並乘以通過每個大小堆的節點數）減少到2，如評論中所述。

來源

2016-03-08 19:23:04

正確答案，我想。通過從上到下的合併，實際上可以達到'O（n）'的複雜度，因爲這些級別的大小構成了一個比例爲「2」的幾何級數。 – WhatsUp

這是O（n）。數學相對簡單;我已經在我的答案中完成了。 – user2357112

特殊的minHeap，如何打印O（n）中的所有n個元素？

回答

相關問題