CODEWITHSUNDEEP
algorithmsortingheapheapsort
verticese
verticese

Reputation: 273

Show heapsort repeats comparisons

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

Upvotes: 0

Views: 387

Answers (1)

Yanhui Zhou
Yanhui Zhou

Reputation: 898

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.

Upvotes: 1

Related Questions