Show heapsort repeats comparisons

Question

how would one prove that heapsort repeats comparisons that it has made before? (i.e. it would perform a comparison that has been done previously) Thanks

Answer 1

The two elements may take comparisons in build heap step(heapify) and also in reorder step in heap sort. This is the wiki.

For example, sort by max-heap:

• origin array: 4 6 10 7 3 8 5
• heapify to a new heap array by shift-up.
  The comparisons: 4<6, 6<10, 4<7, 6<8 (10) (7 8) (4 3 6 5) // each layer is grouped by parenthesis
• re-order step
  • swap the first with the last, put the big one to end
  • reduce the heap size by 1
  • use shift-down
    The comparisons: 5<8, 6<7, 3<6, 3<4, 3<5, 3<4

Because, in the heapify the comparisons based on the order of elements. And after heapify, the order may be not sorted too. So there may be other comparisons.