Heap Sort with and Without Recursion: C program

#include <stdio.h>
void heapify(int a[],int i,int n)
{
    int j;
    for(j=2*i+1; j < n; j = 2*i+1)
    {
        int temp,bci = j;
        if(j+1 < n)
            if(a[j] < a[j+1])
                bci = j+1;
        if(a[i] < a[bci])
        {
            temp=a[i];
            a[i]=a[bci];
            a[bci]=temp;
        }
        else
            break;
        i=bci;
    }
}

void BuildMaxHeap(int a[],int n)
{
    int i,j;
    for(i=n/2;i>=0;i--){
        heapify(a,i,n);
    }
       
}
void sort(int a[],int n)
{
    int temp,i;
    BuildMaxHeap(a,n);
    for(i=1;i<n;i++)
    {
        temp=a[0];
        a[0]=a[n-i];
        a[n-i]=temp;
        heapify(a,0,n-i);
    }   
}
int main()
{
    int n,i;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,n);
    for(i=0;i<n;i++)
        printf("%d  ",a[i]);
}

 ==================OR==============================================
 #include <stdio.h>
int LeftChild(int i)
{
 return (2*(i)+1);
}
void heapify(int *a,int j, int n)
{
 int bci,t;
 for(;LeftChild(j) <n;j=bci) //as long as left child exists
 {
  bci=LeftChild(j);
  if( bci != n-1 &&  a[bci+1] > a[bci])//bci means biggest child index  bci+1 means right child index of i
    bci= bci+1;

  if(a[bci]> a[j])// if big child value is > parent, swap big child value and parent value.
   {
    t=a[j];
    a[j]=a[bci];
    a[bci]=t;
   }
  else    //if big child value is < parent, then this is following max heap property
   break;
 }

}
void Build_maxheap(int *a, int n)
{
 int i;
 for(i=n/2;i>=0;i--)// loop for converting complete binary tree to max heap
  heapify(a,i,n);
// printf("building heap\n");
// for(j=0;j<n;j++)
//  printf("%d\t",a[j]);
}
void HeapSort(int *a, int n)
{
 int dn,t;
 Build_maxheap(a,n);
 for(dn=n-1;dn>0;dn--)
 {
  t=a[0];
  a[0]=a[dn];
  a[dn]=t;
  heapify(a,0,dn);

 }
}
main()
{
 int n,i,a[100];
 printf("enter n value");
 scanf("%d",&n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);
 HeapSort(a,n);
 printf("\n Sorted Array is\n");
 for(i=0;i<n;i++)
  printf("%d\t",a[i]);
}
(OR)
/* Below program is implementation of pseudocode of functions given in "Data Structures and Algorithm Analysis in C" by Mark Allen Weiss -2nd edition*/

#include <stdio.h>
#define LeftChild(i) (2*(i)+1)
void heapify(int *a,int i, int n)
{
    int child,temp,k;
    for(temp=a[i];LeftChild(i)<n;i=child)
    {
        child=LeftChild(i);
        if(child != n-1 && a[child+1]>a[child])
                child++;
        if(temp < a[child])
             a[i]=a[child];
        else
            break;
    }
    a[i]=temp;
}
void heapsort(int *a, int n)
{
    int i,t,j;
    for(i=n/2;i>=0;i--)
        heapify(a,i,n);
// printf("building heap\n");
// for(j=0;j<n;j++)
//  printf("%d\t",a[j]);
    for(j=n-1;j>0;j--)
    {
        t=a[0];
        a[0]=a[j];
        a[j]=t;
        heapify(a,0,j);
    }
}
main()
{
    int n,i,a[100];
    printf("enter n value");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    heapsort(a,n);
    printf("\n Sorted Array is\n");
    for(i=0;i<n;i++)
        printf("%d\t",a[i]);
}

Output:

Heap sort program in java

import java.util.Scanner;
import java.util.Arrays;
public class MyClass
{
    public static void heapify(int a[],int i, int n)
    {
        for(int j=2*i+1;j<n;)
        {
            int maxi=j;
            if(2*i+2 < n)
                if(a[j] < a[2*i+2])
                    maxi=2*i+2;
            if(a[maxi]>a[i])
            {
                int temp=a[i];
                a[i]=a[maxi];
                a[maxi]=temp;
                j=maxi;
            }
            else
                break;
        }
    }
    public static void buildmaxheap(int a[],int n)
    {
        for(int i=n/2;i>=0;i--)
            heapify(a,i,n);
    }
    public static void heapsort(int a[],int n)
    {
        buildmaxheap(a,n);
        for(int index=n-1;index>0;index--)
        {
            int temp=a[0];
            a[0]=a[index];
            a[index]=temp;
            heapify(a,0,index);
        }
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter number of elements");
        int n = sc.nextInt();
        int a[] =  new int[n];
        System.out.println("enter array elements");
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        heapsort(a,n);
        System.out.println("Sorted array");
        System.out.println(Arrays.toString(a));
    }

}
==================
Heapify with recursion
public static void heapify(int a[],int i, int n)
    {
            int lc=2*i+1,maxi;
            if(lc < n)
                maxi=lc;
            else
                return;
            int rc=2*i+2;
            if(rc < n)
                if(a[lc] < a[rc])
                    maxi=rc;
            if(a[maxi]>a[i])
            {
                int temp=a[i];
                a[i]=a[maxi];
                a[maxi]=temp;
                heapify(a,maxi,n);
            }
            else
                return;
    }