Heap Sort

heapsort.c

//Heapify function is used to convert a tree rooted at node root into a max heap

void heapify (int* arr, int root, int size)
{
  int pos = root;
  // location of children
  int left = 2*root + 1;
  int right = 2*root + 2;
  
  if (arr[root] < arr[left])
    pos = left;
  if (arr[root] < arr[right])
    pos = right;
    
  if (pos!=root)
  {
    swap(arr[root],arr[pos])  ;
    heapify (arr, root, size);
  }
}

void heapSort(int* arr, int size)
{
  //Create a heap out of the base array
  for (int i = (size/2-1); i > 0; i--)
    heapify(arr,i,size);
    
  //Sort the elements
  // Basically extract the root and place at the end of the array and swap with the end
  for (int i = size-1; i > 0; i--)
  {
    swap(arr[0],arr[i]);
    
    heapify(arr,0,i);
  }

}