Heap Sort in C - Iterative Algorithm

"Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort." - Wikipedia

#include<stdio.h>
#define maxheapsize 50
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1

MAX_HEAPIFY(int *a, int i, int size)
{
  // Largest of a[i], a[LEFT(i)] and a[RIGHT(i)]
  // is determined and the index is stored in "largest".
  int l, r, largest, temp;
  l = LEFT(i);
  r = RIGHT(i);
  if ((l <= size)&&(a[l] > a[i]))
    largest = l; 
  else largest = i;
  if((r <= size)&&(a[r] > a[largest]))
    largest = r;
  
  // If largest != i, swap a[i] and a[largest]
  // and heapify the subtree rooted at largest
  if(largest != i)
  {
    temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;

    MAX_HEAPIFY(a, largest, size);
  }
}

BUILD_MAX_HEAP(int *a, int size)
{
  int i;

  // 2nd half of the array are leaf nodes, so each is a
  // 1-element heap to begin with.
  for(i = size/2; i > 0; i--)
    MAX_HEAPIFY(a, i, size);
}

HEAPSORT(int *a, int size)
{
  int sortedarray[maxheapsize], actualsize, root;
  int i, s = 0, j, temp;
  actualsize = size;
  
  // Build the heap tree
  BUILD_MAX_HEAP(a, size); 
  
  for(i = size; i > 0; i--)
  { 
    // Save the root to another array
    sortedarray[++s] = a[1];
    root = a[1];

    // exchange a[1](root) and a[i]
    temp = a[1];
    a[1] = a[i];
    a[i] = temp;
    
    size--;
    
    // MAX_HEAPIFY lets the value of a[i] "float down" in
    // the max-heap so that the subtree rooted at index i
    // obeys the max-heap property
    MAX_HEAPIFY(a, 1, size);

    printf("\nHeap tree after removing the largest element %d\n", root);
    for(j = 1; j<=size; j++)
      printf("%d ", a[j]);
    if(size == 0)
      printf("NULL\n");
  }

  // Print the sorted array
  printf("\nSorted array\n");
  for(i = actualsize; i > 0; i--)
    printf("%d ", sortedarray[i]);
}

int main()
{ 
  int a[maxheapsize], n, i;
  printf("\nEnter the size of the array (< 50):");
  scanf("%d", &n);
  printf("\nEnter the elements of the array\n");
  for(i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  HEAPSORT(a, n);

  return 0;
}

Written by Munia Balayil