Heap Sort

Heap Sort

  June 22, 2018    

---

This sorting needs max Heap to sort Array
Algorithm:
As we know heap are balanced tree so they can be constructed using array.

We are already having array , heapify it using root i.e. n/2-1 roots are there so heapify  n/2-1times
After heapify 
Root node will have node greater than its child nodes
We will swap last node with its first node
decrement last node ,change  root to next element and heapify again


Code:

 void buildHeap(int a[], int n)
    {
        for(int i=n/2-1;i>=0;--i)
        heapify(a,n,i);
        for(int i=n-1;i>=0;--i)
        {
            int temp=a[0];
            a[0]=a[i];
            a[i]=temp;
            heapify(a,n,0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int a[], int n, int i)
    {
        int l=2*i+1;
        int r=2*i+2;
        int max=i;
        if(l<n && a[l]>a[max])
        max=l;
        if(r<n && a[r]>a[max])
        max=r;
        if(max!=i)
        {
            int temp=a[i];
            a[i]=a[max];
            a[max]=temp;
            heapify(a,n,max);
        }
    }