CODEWITHSUNDEEP
data-structuresheapheapsort
Pooja Kulkarni
Pooja Kulkarni

Reputation: 132

Heap sort, min-heap to be used or max?

For heap sort, if we want to sort an array in an ascending order, then should the heap be converted in a max-heap or a min-heap?

Upvotes: 1

Views: 807

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

Either approach can be made to work. Typically, you'd use a max heap ordered so that the largest element is in the far left side of the array. That way, when you dequeue and remove the elements from the heap to put them in their final positions, you can place them from right to left (in descending order) on the far side of the array without stepping on top of the other heap elements.

In principle you could also build a min heap with the minimum element in the far right position, then dequeue small elements and move them to the far left side, though I've never seen this done before.

Upvotes: 3

Related Questions