algorithm - 显示堆排序重复比较

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
  • 使用下移
    比较:5<8, 6<7, 3<6, 3<4, 3<5, 3<4

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