CODEWITHSUNDEEP
algorithmsortingheapheapsort
qwerty_99
qwerty_99

Reputation: 798

heap sort and reverse heap sort with max/min heap

I just want to check if I understood what the professor and online ressources said.

For a heapSort algorithm, the index of the first element starts at 0.

For a max heap, percolate down should swap the maximum child with its parent if the child is bigger than the parent, so something like (this is for an assignement so I tried to post as little code as possible):

def percolateDownMaxHeap( array, hole, length):
    while hole * 2 < size - 1:
        left = 2*hole + 1
        right = left + 1

        max = left

        if (left < size - 1) and (array[right] > array[left]):
            max = right

        if (array[max] > array[hole]):
            swap(array, hole, max)

        else:
            break

        hole = max

So in the end, the maximum element should be at index 0.

If this is correct, what I don't understand is the heapSort implementation:

def heapSort(array):
    i = len(array) / 2
    while i >= 0:
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

    i = len(array) - 1

    while i > 0:
        swap( array, 0, i );
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

Isn't percolate down in a max heap supposed to put the largest element at index 0? In this case why not use percolate down on a min heap? The code works but I'm not sure if I got it right or if I implemented a max heap instead of a min heap

Thanks

Upvotes: 1

Views: 665

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

Isn't percolate down in a max heap supposed to put the largest element at index 0?

It does. Then your code swaps it past the heap, so each successive swap places the next largest element where it belongs.

In this case why not use percolate down on a min heap?

That would get the min element in the right position, but the heap still needs that position in the array, so it's not clear what to do for the next element.

Upvotes: 2

Related Questions