在堆中多次使用相同的密鑰

Question

在一堆（無論是最大堆還是最小堆）中，是否可能存在兩次或多次相同的密鑰？

這種情況如何破壞O(n)的時間複雜度makeheap()和O(log(n))插入和刪除？

例如： 以下堆有效嗎？

1 

/\ 

1 1 

Answer 1

有時候理論擾動參數是很好回答這類的問題。想象一下堆中的每一個元素，當元素被插入到堆中時，您還會存儲一個到目前爲止已經完成的操作數量的「索引」，無論是構建或訪問堆棧中的任何內容。因此，堆中的每個元素都有一個次要唯一標識，當堆中的兩個值相等時，您可以使用它來打破「連接」，並且您仍然需要對它們進行比較。那麼顯然這個堆將像往常一樣運行，並且具有相同的運行時間保證。找出這樣的擾動是圍繞這些退化問題的簡單方法，特別是在計算幾何問題時，如果你不想要一個線上的3個點，或者一個圓上有4個點等等。

但是，我給了你對你的問題有點迂迴的回答。我相信真正的事實是，在堆操作中，只要被交換的子元素小於或等於它的父元素，就可以隨意決定哪些元素與父元素進行交換（假設min-堆），並且一切都應該正常工作。唯一可能讓事情變得更加複雜的是，如果出於某種原因，您想要立即將所有關係以最小值排除在堆外。但我相信，即使這並不是什麼大不了的事情。

Answer 2

是否有可能有相同的密鑰兩次或多次？

是的，這是可能的。

這種情況如何破壞時間複雜性？

它不能。看看你選擇的堆實現。爲了導出O-符號，證明覆雜性的上限是簡單而直接的，而不對所涉及的值作任何假設。這意味着，例如，值可以重複，而不會影響複雜性。