斯普利特二項堆

我試圖想到一個主意，使一個新的分支操作，通過給予Binomial heap。斯普利特二項堆

問題是如何在最小運行時間內將二叉堆（size n）拆分成大小爲k（k < n）的二項式堆和大小爲n-k的二項堆。

會是什麼有這種拆分操作的好處（還有一個原因堆是分裂50/50）？你試過什麼了？ – Davidann 2011-05-10 18:12:02

你可以找到O(n)時間中位數算法的中位數一組的kth最大的元素。 Source。

當你有一個值，你可以閱讀從原來堆的所有值（不需要解壓，它們的順序讀取上並不重要，只有在新的陣列寫。這有額外的好處不要混淆原始堆，Yay），並將其放入大堆或小堆中，具體取決於它們與kth值之間的關係。每次提取是O(1)併發生n次。每個插入是O(lg n)並且發生n次。

Total running time: n + n + n lg n = O(n lg n) 
        | |  | 
      selection | inserts 
        extraction

2011-05-10 18:12:28 corsiKa

如果你已經執行O（nlogn）操作，爲什麼不從原始堆排序的所有值，發現第k個號碼，插入所有入堆數比大，和所有小於該到另一個堆？似乎比使用中值算法更簡單... – Gal 2011-05-11 08:17:28

@Gal因爲沒有必要。你的函數以最小的努力獲得了30％的速度提升（算法已經爲我們編寫了，開發時間很短）。另外，你甚至不需要從原始數組中提取。你可以將它們全部閱讀並插入。這又提高了30％。我剛剛意識到這一點。 – corsiKa 2011-05-11 08:20:08

您可以通過簡單地從原來的堆取出k個元素，並將它們轉移到一個新的不同的堆在K *的log（n）做到這一點。（這個假設堆是最小堆，如果它是一個最大堆那麼它可以在（NK）的log（n）來完成同樣的方式）

2011-05-11 08:21:26 Gal

回答