如果你有一個大小爲14的二項堆，你怎麼知道哪個節點是根節點？

enter image description here 如果你有一個大小爲14的二項堆，你怎麼知道哪個節點是根節點？

嗨，大家好，我只是有一個關於這個圖的問題。如何判斷哪個節點是根節點，並且我該如何heapify這樣的事情？

謝謝。

編輯：對不起，當我說heapify我的意思是做一個最大的堆。通常有一個常規的堆，我會從左到右，從第一個不是葉節點的節點開始向下篩選。雖然我沒有看到我能做到這一點。

來源

2012-12-09 CoffeeIsProgramming

我不確定你在問什麼。在一般情況下，二項堆不是一棵樹，它是一棵樹的集合。它沒有「根節點」。即使它碰巧是一棵樹，它也應該已經被堆砌，根節點是最小的關鍵節點。這全部由Binomial Heap定義。 – AnT

我認爲你想把二項堆看作一個二進制堆，這是行不通的。

A Binary Heap可以存儲在一個沒有顯式鏈接的數組中 - 鏈接隱含在數組中的位置。無序數組可以「堆積」，重新排序以在O（n）時間內生成有效的二進制堆。這是二進制堆的關鍵優勢 - 有一個使用內存的輕量級實現。

我從來沒有實施過Binomial Heap，儘管我已經研究過它們，那是前一陣子。不過，我非常自信，二項堆不是二進制堆，不能以這種方式實現。二項堆有其自身的優勢，但它們並沒有保留二元堆的所有優點。如果二項堆普遍優越，那麼沒有人會關心二元堆。

IIRC，二項式樹的正常實現（基於二項堆）是每個父節點和一個鏈表的根鏈接列表。這些鏈接列表使用顯式鏈接。這就是你如何支持每個節點的k個孩子，沒有k的上限。

二進制堆的重要額外操作是合併。如果二項堆被存儲在一個帶隱式鏈接的數組中，合併顯然需要大量的複製 - 將一個數組中的項目複製到另一個數組中以便開始。因此，高效的合併是不可能的 - 二項堆的關鍵優勢將會喪失。但是，將兩個二叉樹組合成一個是O（1）指針操作（將項添加到鏈表的頭部），因此可以將兩個二項式堆合併爲O（log n）二項樹非常有效地合併。

這有點像排序數組和二叉搜索樹之間的區別。當然，排序後的數組有優勢，但也有侷限性。如果您只需修改一個或兩個鏈接而不移動數組中的項目，則某些操作效率更高。有時候你不需要這些操作，而且避免鏈接的需要和二進制搜索排序數組的效率更高，這相當於用隱式鏈接搜索完美平衡的二叉搜索樹。

來源

2012-12-09 16:13:37 Steve314

概念上，根應該是唯一沒有祖先的節點 - 在圖的情況下爲1。

來源

2012-12-09 04:57:24

這是一個二項堆，它沒有一個根，而是一組根（因爲二項堆是一組二叉樹）。

你是什麼意思「做一個最大的堆」？最大的堆和二項堆是相互靠得很近，因爲java和javascript是。

如果您提取最少n次，您可以獲得一個最大堆的排序數組。複雜度爲O（n * log（n））。

來源

2012-12-09 15:32:13 Thomash

「最大堆」是*任何*堆，其中最高優先級項目是最大（最大）項目。這可能是一個二叉堆，就像它可能是一個二進制堆一樣容易。最大。與最小。堆獨立於堆數據結構。也就是說，從最小堆變爲最大堆是微不足道的（交換'<' for '>'），所以不要相信Adam真的在問他在問什麼。儘管如此，關於排序數組的點也是+1。 – Steve314

如果你有一個大小爲14的二項堆，你怎麼知道哪個節點是根節點？

回答

相關問題