CODEWITHSUNDEEP
algorithmdata-structuresheapsort
Fares_Hassen
Fares_Hassen

Reputation: 103

Heaps/Heap-sort DSA swap parent with equal value childs

during a heapify-down co-routine, if a parent in a max heap is less than both children and the children are equal in value. which child should I pick to swap with? and will it affect the heapsort algo?

Upvotes: 1

Views: 157

Answers (1)

John Bollinger
John Bollinger

Reputation: 181199

which child should I pick to swap with?

The job of such a routine is to restore the heap criterion. When a parent node has two equal children and it is out of order with respect to them, the routine can achieve that with either choice of child. This is one of the characteristics that make heap sort as efficient as it is.

will it affect the heapsort algo?

For some specific instances of such choices, one alternative is cheaper than the other. However, even if, for a particular input, the routine happens to make the worse choice at every opportunity, that does not prevent the overall sort from computing the correct result in O(n log n) steps.

Upvotes: 3

Related Questions