在刪除大小爲N的堆中沒有重複鍵的最大操作期間必須交換的項目的最小數量是多少？

Question

這個問題我在Sedgewick的書中遇到過。在他的網站上，他說答案是2，但我不明白如何達到2，因爲爲了消除最大限度，我們需要首先與最後一個交換最大元素，減少N，然後沉入最後一個元素從頂部進入它的位置，這需要logN交換。那麼，你如何達到2？

交易所&刪除-MAX：

然後我們需要往下沉，使L節點，這意味着我們需要做更多的logN個交流。

Answer 1

下面是15個節點的示例。這個想法是：有根的兒子是大的（讓左邊的兒子變大），但是其他的後裔比正確的兒子小得多。那麼你只會交換兩次。

    100 
     99     90 
    9  8   89  88 
7 6 5 4  87 86 85 84 

你會切換84, 100然後99, 84就大功告成了。兩次掉期。

對於n > 3，在第一次交換之後，兩個根的兩個兒子都不會大於新根（否則它不是一堆堆）。所以你必須做另一個交換。作者很可能意味着寫掉掉，而不是項目。