C Program to Implement Heap Sort

This C program sorts a given array of integer numbers using Heap Sort technique.

Depending upon the value of MAX we create an integer array with numbers ranging from 0 to MAX – 1. Using random_shuffle function we randomize the array and the sort it using heap sort algorithm. Time Complexity of this algorithm is O( nlog(n) ).

Here is the source code of the C program to sort integers using Heap Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to sort an array using Heap Sort technique

```
 */
```
```
 
```
```
#include<stdio.h>
```
```
#include <stdlib.h>
```
```
#define MAX 25
```
```
 
```
```
void random_shuffle(int arr[])
```
```
{
```
```
    int i, j, temp;
```
```
    srand(time(NULL));
```
```
    for (i = MAX - 1; i > 0; i--) {
```
```
         j = rand()%(i + 1);
```
```
         temp = arr[i];
```
```
         arr[i] = arr[j];
```
```
         arr[j] = temp;
```
```
    }
```
```
}
```

void  max_heapify(int a[], int i, int heapsize)

```
{
```
```
    int tmp, largest;
```
```
    int l = (2 * i) + 1;
```
```
    int r = (2 * i) + 2;
```

    if ((l <= heapsize) && (a[l] > a[i]))

```
         largest = l;
```
```
    else
```
```
         largest = i;
```

    if ((r <= heapsize) && (a[r] > a[largest]))

```
         largest = r ;
```
```
    if (largest != i) 
```
```
    {
```
```
         tmp = a[i];
```
```
         a[i] = a[largest];
```
```
         a[largest] = tmp;
```

         max_heapify(a, largest, heapsize);

```
    }
```
```
 
```
```
}
```

void  build_max_heap(int a[], int heapsize)

```
{
```
```
    int i;
```
```
    for (i = heapsize/2; i >= 0; i--)
```
```
    {
```
```
         max_heapify(a, i, heapsize);
```
```
    }
```
```
 
```
```
}
```
```
void heap_sort(int a[], int heapsize)
```
```
{
```
```
    int i, tmp;
```
```
    build_max_heap(a, heapsize);
```
```
    for (i = heapsize; i > 0; i--) 
```
```
    {
```
```
        tmp = a[i];
```
```
        a[i] = a[0];
```
```
        a[0] = tmp;
```
```
        heapsize--;
```
```
        max_heapify(a, 0, heapsize);
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int i, r, heapsize;
```
```
    int a[MAX];
```
```
    for (i = 0; i < MAX; i++)
```
```
        a[i] = i;
```
```
    heapsize = MAX - 1;
```
```
    random_shuffle(a);
```
```
    printf("\n");
```
```
    heap_sort(a, heapsize);
```
```
    for (i = 0; i < MAX; i++)
```
```
        printf("%d ", a[i]);
```
```
    return 0;
```
```
}
```

$ gcc heapsort.c -o heapsort
$ ./heapsort
 
Sorted numbers are: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C program to Sort Integers using Quick Sort Technique

» Next - C Program to Sort Linked List using Merge Sort

Related Posts:

Recommended Articles: