從最小堆切換到最大堆而不重新排列內部數組

Question

假設我們有一個最小堆，其中一些元素滿足堆屬性。 如果將算法從最小堆更改爲max max堆會發生什麼情況，而不重新排列內部數組？

也就是說，如果我保持數組不變，當我將一個元素追加到內部數組時會發生什麼？

Answer 1

從Wikipedia請看下面的例子：

這樣做的數組表示應該是這樣的：

[1, 2, 3, 17, 19, 36, 7, 25, 100] 

現在我們「變」從最小堆到最大，但沒有重新安排元素並插入一個新元素「25」。數組的位置爲9，因此父節點在位置4處爲「19」。

插入之後，我們必須反覆比較新項目與其父項以確保堆屬性（現在max-heap => parent必須大於兒童）。因此，我們必須將「25」與「19」，「2」和「1」交換，直到它成爲根節點。

現在max-heap屬性適用於根節點（其子節點確實更小），但不適用於其他節點。 「3」仍然是「7」的父親，並且違反了最大堆條件。

總而言之：做你所描述的並不會改變最小堆到最大堆。

Answer 2

你只需要把這個堆搞定。

你必須重新heapify（這可以在時間O（N））完成。