在大小为 N 且没有重复键的堆中，在删除最大操作期间必须交换的最少项目数是多少？
What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N with no duplicate keys?
这个问题是我在塞奇威克的书中遇到的。在他的网站上，他说答案是2，但是我不明白如何实现2，因为要删除最大值我们需要先将max元素与最后一个交换，减少N，然后下沉最后一个从顶部向下到它的位置，这需要 logN 交换。那么，如何实现 2？
交换和删除-max:
然后我们需要下沉，那个L节点，也就是说我们需要做logN次交换。
这里是 15 个节点的示例。这个想法是：让根的儿子大（让左边的儿子大），但其他左边的后代比右边的小得多。那么你只会交换两次。
100
99 90
9 8 89 88
7 6 5 4 87 86 85 84
您将切换 84, 100 然后 99, 84 就完成了。两次互换。
对于n > 3，在第一次交换后，根的两个儿子不可能都不大于新根（否则它不是一个堆开始） .所以你必须再做一次交换。作者很可能是想写交换，而不是物品。
问题问的是必须兑换的物品数量，不是兑换次数。最低兑换次数为1次，一次兑换需要兑换2次。
示例：
3
1 2
这里，两个元素之间只有一次交换：3和2。
这个问题是我在塞奇威克的书中遇到的。在他的网站上，他说答案是2，但是我不明白如何实现2，因为要删除最大值我们需要先将max元素与最后一个交换，减少N，然后下沉最后一个从顶部向下到它的位置，这需要 logN 交换。那么，如何实现 2？
交换和删除-max:
然后我们需要下沉，那个L节点，也就是说我们需要做logN次交换。
这里是 15 个节点的示例。这个想法是：让根的儿子大（让左边的儿子大），但其他左边的后代比右边的小得多。那么你只会交换两次。
100
99 90
9 8 89 88
7 6 5 4 87 86 85 84
您将切换 84, 100 然后 99, 84 就完成了。两次互换。
对于n > 3，在第一次交换后，根的两个儿子不可能都不大于新根（否则它不是一个堆开始） .所以你必须再做一次交换。作者很可能是想写交换，而不是物品。
问题问的是必须兑换的物品数量，不是兑换次数。最低兑换次数为1次，一次兑换需要兑换2次。
示例：
3
1 2
这里，两个元素之间只有一次交换：3和2。