显示堆排序重复比较

Question

如何证明堆排序重复了之前进行的比较？ （即它会执行之前已经完成的比较） 谢谢

Answer 1

这两个元素可能在构建堆步骤（heapify）中进行比较，也可能在堆排序的重新排序步骤中进行比较。这是the wiki。

例如，按最大堆排序：

• 原始数组：4 6 10 7 3 8 5
• heapify 通过 shift-up.
  到一个新的堆数组 比较：4<6、6<10、4<7、6<8 (10) (7 8) (4 3 6 5) // 每层按括号分组
• 重新排序步骤
  • 先调后调，大的放在最后
  • 将堆大小减少 1
  • 使用shift-down
    比较：5<8, 6<7, 3<6, 3<4, 3<5, 3<4

因为，在heapify中，比较是基于元素的顺序。而在heapify之后，顺序可能也没有排序。所以可能还有其他比较。