The following code shows a C Program to Implement Heap Sort.

Sorting in Descending Order

// Implementing heap sort using max heap

#include <stdio.h>
void HeapSort(int myarray[], int Length);
void Heapify(int myarray[], int Length, int x);
void Swap(int myarray[], int x, int y);
void Heapify(int myarray[], int Length, int x)
{
    int max, left, right;
    max=x;
    left=2*x+1;
    right=2*x+2;
    
    if(left<Length && myarray[left]<myarray[max])
    {
        max=left;
    }
    if(right<Length && myarray[right]<myarray[max])
    {
        max=right;
    }
    if(max !=x)
    {
       Swap(myarray, x, max);
       Heapify(myarray, Length, max);
    }
}
void HeapSort(int myarray[], int Length)
{
    int i, n;
    i=Length/2-1;
    while(i>=0)
    {
        Heapify(myarray, Length, i);
        i--;
    }
    i=Length-1;
    while(i>=0)
    {
        Swap(myarray, 0, i);
        Heapify(myarray,i, 0);
        i--;
    }
}
void Swap(int myarray[], int x, int y)
{
    int t=myarray[x];
    myarray[x]=myarray[y];
    myarray[y]=t;
}
int main()
{
    int i, elements_count;
    int myarray[]={13, 11, 19, -23, -8, 44, 67, 6, -5, -34, 12, -1, 20};
    elements_count=sizeof(myarray)/sizeof(int);
    printf("Array before sorting....\n");
    for(i=0;i<elements_count;i++)
    {
        printf("%d ", myarray[i]);
    }
    HeapSort(myarray, elements_count);
    printf("\n\n");
    printf("Array after sorting....\n");
    for(i=0;i<elements_count;i++)
    {
        printf("%d ", myarray[i]);
    }
    return 0;
}

Output

Array before sorting….
13 11 19 -23 -8 44 67 6 -5 -34 12 -1 20

Array after sorting….
67 44 20 19 13 12 11 6 -1 -5 -8 -23 -34

Sorting in Ascending Order

// Implementing heap sort using max heap

#include <stdio.h>
void HeapSort(int myarray[], int Length);
void Heapify(int myarray[], int Length, int x);
void Swap(int myarray[], int x, int y);
void Heapify(int myarray[], int Length, int x)
{
    int max, left, right;
    max=x;
    left=2*x+1;
    right=2*x+2;
    
    if(left<Length && myarray[left]>myarray[max])
    {
        max=left;
    }
    if(right<Length && myarray[right]>myarray[max])
    {
        max=right;
    }
    if(max !=x)
    {
       Swap(myarray, x, max);
       Heapify(myarray, Length, max);
    }
}
void HeapSort(int myarray[], int Length)
{
    int i, n;
    i=Length/2-1;
    while(i>=0)
    {
        Heapify(myarray, Length, i);
        i--;
    }
    i=Length-1;
    while(i>=0)
    {
        Swap(myarray, 0, i);
        Heapify(myarray,i, 0);
        i--;
    }
}
void Swap(int myarray[], int x, int y)
{
    int t=myarray[x];
    myarray[x]=myarray[y];
    myarray[y]=t;
}
int main()
{
    int i, elements_count;
    int myarray[]={13, 11, 19, -23, -8, 44, 67, 6, -5, -34, 12, -1, 20};
    elements_count=sizeof(myarray)/sizeof(int);
    printf("Array before sorting....\n");
    for(i=0;i<elements_count;i++)
    {
        printf("%d ", myarray[i]);
    }
    HeapSort(myarray, elements_count);
    printf("\n\n");
    printf("Array after sorting....\n");
    for(i=0;i<elements_count;i++)
    {
        printf("%d ", myarray[i]);
    }
    return 0;
}

Output

13 11 19 -23 -8 44 67 6 -5 -34 12 -1 20

Array after sorting….
-34 -23 -8 -5 -1 6 11 12 13 19 20 44 67


Further Reading

50+ C Programming Interview Questions and Answers

C Program to Find Factorial of a Number