Technique: Build Heap and Heap Sort Animation

   Step by step animation. For the programming beginners to get a better understanding of heap and heap sort.
   In the animation, the heap in tree structure just let you know how it works. The entire coding is using array rather than binary tree. (Click snail button to start animation and click it again to go back to the first page)
   For an element with index i in the array 
   Its parent index is:  (i-1)/2
   Its left child index is: 2*i+1
   Its right child index is: 2*i+2





 Cost: O(nlogn)
 Worst case: O(nlogn)
 Best case: O(nlogn)

Heap sort code in C++:

void swap(int i, int j,int a[])

  {

         int temp;

         temp=a[i];

         a[i]=a[j];

         a[j]=temp;

  }

void heapify(int i,int a[],int heapSize)

{

       int temp=i;

       while(i*2+1<=heapSize-1)

       {

           if(i*2+2<=heapSize-1&&a[i*2+2]>a[i*2+1])

           {

               i=i*2+2;

           }

           else i=i*2+1;

           if(a[i]>a[temp])

           {

              swap(i,temp,a);

              temp=i;

           }

           else break;

       }

}

void BuildMaxHeap(int a[],int heapSize)

{

         int i=(heapSize-1)/2;

        while(i>=0)

        {    

          heapify(i,a,heapSize);

          i--;

        }

}

void heapSort(int a[],int heapSize)

{

     for(int i=heapSize;i>0;i--)

     {

         swap(0,heapSize-1,a);

         heapSize--;

         heapify(0,a,heapSize);

     }

}

int main()

{

int heapSize=7;

int a[]={25,49,8,25,21,16,32};

BuildMaxHeap(a,heapSize);

heapSort(a,heapSize);

}


More technique animations:

Quick Sort
Binary Search 
Merge Sort 
Bubble Sort 
Selection Sort