HeapSort247 views

AlgoPill 
 function heapSort(list){
    // left child 
    function left(p){
        return 2*p+1;
    }
    // right child
    function right(p){
        return 2*p+2;
    }
    // parent node
    function parent(c){
        return Math.floor((c-1)/2);
    }
    // restore heapproperty assuming that child trees of x are max-heaps
    function heapify(list,x,size){
       var largest = x,tmp;
        while(x>=0){
            if(right(x)<size&&list[right(x)]>list[largest]){
                largest = right(x);
            }
            if(left(x)<size&&list[left(x)]>list[largest]){
                largest = left(x);
            }
           if(largest==x){
               break;
           }
           tmp =  list[largest];
          list[largest] = list[x];
          list[x] = tmp;
          x = largest;
        }
    }

   // variable declarations
   var i,tmp,size;

   // create heap datastructure 
   for(i=parent(list.length-1);i>=0;i--){
       heapify(list,i,list.length);
   }

   // sort the values by pulling out max value from the top of heap
   size = list.length;
   while(size>0){
      //swap 
       tmp = list[0];
       list[0] = list[size-1];
       list[size-1] = tmp;
       heapify(list,0,size-1);
       size--;
   }
   return list;
}

Problem Statement: Given a list of number arrange them in ascending order
Solution: Heap sort algorithm works by first arranging the numbers in a max heap and then by removing element from the top of the heap one by one.
Max-Heap is a binary tree data structure with a property that value at any node is greater than any value in its two child (subtrees) threes. Heap data structure can be maintained in an array such that root of the tree is stored at the begin the first element of the array i.e. at the zeroth index and a node of tree is stored at index i then its left child is stored at 2*i+1 and its right child is stored at 2*i+2 and similarly parent of a child at index i is floor((i-1))/2.

Given a list of numbers in an array, the array can be rearranged in-place such that the elements in array represent the Max-Heap data structure. This is done by iteratively calling the heapify routine.
Heapify routine restores the heap property for a tree rooted at x given that subtrees at left(x) and right(x) satisfy max-heap property but the element at x is either less than right and/or left child.

Heapify routine is simple. it compared the values at x , right(x) and left(x) and finds the maximum, it swaps the value at x with either right(x) or left(x). This swap makes sure that value at x is larger than any value at right or left subtrees and thus restoring the max-heap at x. But this swap could violate heap property of right(x) or left(x) subtrees ( to whichever we swapped the x with) . To fix this we again call heapify for one of these and this process is repeated untill all subtrees also statisfy heap property.

Heapify routine is a key routine in heap sort. It is used to covert input array of numbers into a max heap. This is done by calling heapify starting from lowest parent node which should be parent of the last node in the heap that is parent(length-1) for all the node till the root node that is zeroth element.

Once heap is formed we swap the root node with the last element in the root. The last element is then effectively taken out of heap and size of heap reduces by one. Then heapify is called at the root node to restore the heap property with the new element at the root node. We repeat this process until we have more that one element in the heap. Since heap is a max heap and we always remove the node from root and swap it with the last item on the heap, at the end of this process we will get numbers arranged in ascending order.

The runtime complexity of this is O(N*logN). Heapify routine take O(log(x)) and since we call heapify on each element starting from parent(n-1) to 0th element, total time to create heap takes O(nLOGn) time. Removing the root node and restoring the heap property again takes O(logN) time and since we do this for all the elements in the input, total time to sort elements in take O(NlogN)

Post a Comment

You must be logged in to post a comment.