Heap Sort_Complete Binary Tree

Question

In Heap sort perform two steps

1. Build a heap, using the elements of (say unsorted) Array.
2. Repeatedly Delete the Root element of the Heap formed in first phase and append those element at the last of the array

But if in step 1 we get a sorted array (after building Heap) then why there is a need for step 2?

I had posted a question about Heap sort and i am expecting someone to address my query

Answer 1

The most important thing to understand about heaps is that building a heap does not sort the array. Rather, it arranges the array in such a way that it's very efficient to find and remove the smallest (in a min-heap, the largest in a max-heap) element.

For example, imagine you have the array [4,7,6,1,3,2,5]. Heapsort typically creates a max heap if it's sorting in ascending order. The typical build-heap function would create this max heap:

        7
     4     6
    1 3   2 5

That heap is expressed in the array as [7,4,6,1,3,2,5], which is obviously not sorted. But it's arranged so that every node is smaller than its parent. The largest value is at the root. We can quickly (in O(log n) time) remove the largest item and rearrange the heap so that the new largest element is in the first position.

What Heapsort does is swap the root value (which is by definition the largest item in the heap) with the last value in the heap to create:

        5
     4     6
    1 3   2 7

Then it reduces the count by one, and sifts the new root node down to where it belongs in the heap. After that's done, you're left with the heap:

        6
     4     5
    1 3   2

The array, of course, still contains the value 7. It's just not "in the heap" anymore because the count has been reduced by 1. The resulting array is [6,4,5,1,3,2,7].

Heapsort continues in this fashion: swap the root node with the last node in the heap, reducing the count and sifting the new root node down to where it belongs. So the sequence becomes:

        2                   5
     4     5    ==>      4     2
    1 3   6             1 3
            [5,4,2,1,3,6,7]

        3                   4
     4     2    ==>      3     2
    1 5                 1
            [4,3,2,1,5,6,7]

        1                   3
     3     2    ==>      1     2
    4
            [3,1,2,4,5,6,7]

        1                   2
     3     2    ==>      1

            [2,1,3,4,5,6,7]
        1       ==>         1
      2
            [1,2,3,4,5,6,7]

Note also that there is more than one valid heap for any group of non-identical elements. For example, below is another perfectly valid max heap:

        7
     5     6
    1 4   3 2

Again, each child is larger than its parent. This heap is represented in the array as [7,5,6,1,4,3,2], but by following the algorithm I demonstrated above, (swap root with the last node, reduce the count, and sift down), you'll end up with a sorted array.

The actual arrangement when building a heap will depend on the order of the initial array and on the implementation of your build-heap algorithm. In addition, the heap that results from running the build heap algorithm will be different than what is created if you build the heap by repeated insertion.