algorithmheapheapsort

Max Heapify Algorithm

I am bit confused. If I have an array I have to build a tree. To compare the childern I have to know how large my array is in this case its N = 6 so I have to divide it by 2 so I get 3. That means I have to start from index 3 to compare with the parent node. If the child is greater than the parent node then I have to swap it otherwise I don't have to. Then I go to index 2 and compare with the parent if the children is greater than the parent node then I have to swap it. Then index 1 I have to compare with the children and swap it if needed. So I have created a Max heap. But know I don't get it but why do I have to exchange A1 with A[6] then A1 with A[5]. Finally I dont get the Max heap I get the Min Heap? What does Heapify mean?

Thanks alot I appreciate every answer!

One of my exercise is Illustrate the steps of Heapsort by filling in the arrays and the tree representations

enter image description here

Solution

  • There are many implementations of a heap data structure, but one is talking about a specific implicit binary heap. Heap-sort is done in-place, so it uses this design. Binary heaps require a compete binary tree, so it can be represented as an implicit structure built out of the array: for every A[n] in zero-based array,

    Say one's array is, [10,14,19,21,23,31], is represented implicitly by the homomorphism, using the above rules, as,

    The rules applied to [10,14,19,21,23,31].

    This is not following the max-heap invariants, so one must heapify, probably using Floyd's heap construction which uses sift down and runs in O(n). Now you have a heap and a sorted array of no length, ([31,23,19,21,14,10],[]), (this is all implicit, since the heap takes no extra memory, it's just an array in memory.) The visualisation of the heap at this stage,

    The heap [31,23,19,21,14,10].

    We pop off the maximum element of the heap and use sift up to restore the heap shape. Now the heap is one smaller and we've taken the maximum element and stored unshifted it into our array, ([23,21,19,10,14],[31]),

    The heap [23,21,19,10,14].

    repeat, ([21,14,19,10],[23,31]),

    The heap [21,14,19,10].

    ([19,14,10],[21,23,31]),

    The heap [19,14,10].

    ([14,10],[19,21,23,31]),

    The heap [14,10]

    ([10],[14,19,21,23,31]),

    The heap [10].

    The heap size is one, so one's final sorted array is [10,14,19,21,23,31]. If one used a min-heap and the same algorithm, then the array would be sorted the other way.