Heap Sort in C


In heap sort, we create a heap. Heap is a type of binary tree. There are two types of heap:

  1. Max-heap.
  2. Min-heap.

Max-heap

When the value at any node of tree is greater than that of its all children then the tree is called max-heap.

Min-heap

When the value at any node of tree is smaller than that of its all children then the tree is call min-heap.

In heap sort first step is to build a heap from an array. For that take an array and build a tree out of it. We will build max heap.

Array

16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19

 

  • To build a max-heap you need to take (n-1) level and compare it with the n level which is leaf node.
  • Elements at (n-1) level are 15, 19, 18, 38. Compare them with their child. Only 15 and 19 have a child. We get a new tree.

  • Similarly root elements at 2nd level are compared with 3rd level.
  • 26 is greater than 11 and 38 is greater than 29.

We get a max-heap


Now we will see how to remove root element to use this heap to sort our array.

Array to be sorted

16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19

Max-heap

This max heap can be represented using an array given below

38, 26, 29, 17, 20, 18, 16, 11, 15, 5, 19

Now we need to remove the root element to get the maximum element from an array

  • Again build heap after removing the root.
  • Now arrange 26, 29, 17, 20, 18, 16, 11, 15, 5, 19 to build max-heap.

Now again remove the root element and it would be our 2nd largest element.

 

By repeating these steps we can take out root elements and then we get a sorted array.

Heap Sort Algorithm Implementation

To sort an array using heap sort we need to build a max-heap.

Array to be sort

int a[] = {10000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};

Note: Place an element of large value at 0th element. It would make our calculations easier.

Create a max_heap() function

In this function we take the length of the array as a last element. This helps to specify the limit of the heap. If we divide last by 2 then we get the parent of the last element which is of our interest and is in the last level.

void max_heap(int a[], int last){
    int i;
    for(i=last/2; i>0; i--){
        helper_maxheap(a, i, last);
    }
}

Now all the elements at index <= 5 have one or more child. So we need to run a for loop from index = last/2 to 1. In max-heap value at all the parents node must be greater than the value at children node.

Call helper_maxheap() method to build max-heap

  • Get the first child of the parent using
    child = parent*2;
  • Check to see that the child exist in the array.
     while(child<=last){
     }
    
  • Check to see weather the left child is larger or right child.
     if((child+1)<=last && a[child+1]>a[child])
            child++;
  • Check if the larger child is greater than the parent. If yes then swap.
     if(a[child]>a[parent]){
            temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
        }
    
  • Now the current parent-child has been checked. Now make sure that the tree below the current node satisfy the heap.
     parent = child;
     child = parent*2;
    

Complete code for helper_maxheap() function.

    void helper_maxheap(int a[], int parent, int last){
    int child, temp;
    child = parent*2;
    while(child<=last){
    if((child+1)<=last && a[child+1]>a[child])
        child++;
    
    if(a[child]>a[parent]){
        temp = a[child];
        a[child] = a[parent];
        a[parent] = temp;
    }
    /* current parent-child is checked. Now let a child be parent and its children if exists
   will be located at (parent*2) index 
   */
    parent = child;
    // new child to be checked
    child = parent*2;
    
    }
    
}

Now we have an array which we want to sort.

 int a[] = {1000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};

Create heap_Sort() function which will take array containing max-heap as an argument.

We will remove the largest element which is at 1st index of an array from our max-heap. We will swap the 1st element with the last element of max-heap.

  • Swap the 1st and last element.
  • Decrement last index.
  • Call helper_maxheap() to heapify the max-heap.
void heap_Sort(int a[], int last){
    int temp;
    while(last>1){
        temp = a[1];
        a[1] = a[last];
        a[last] = temp;
        last--;
        
       helper_maxheap(a, 1, last);
        
    }
}

Complete code for heap sort

#include <stdio.h>
#include <string.h>
void max_heap(int[], int);
void helper_maxheap(int[], int, int);
void heap_Sort(int[], int);
void heapify(int[], int);
main()
{
   int a[] = {1000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};
   int i;
   max_heap(a, 11);
   for(i =1;i<=11;i++){
       printf("%d, ", a[i]);
   }
   heap_Sort(a, 11);
printf("\n");
   for(i =1;i<=11;i++){
       printf("%d, ", a[i]);
   }
   
}
void max_heap(int a[], int last){
    int i;
    for(i=last/2; i>0; i--){
        helper_maxheap(a, i, last);
    }
}
void helper_maxheap(int a[], int parent, int last){
    int child, temp;
    child = parent*2;
    while(child<=last){
    if((child+1)<=last && a[child+1]>a[child])
        child++;
    
    if(a[child]>a[parent]){
        temp = a[child];
        a[child] = a[parent];
        a[parent] = temp;
    }
    
    parent = child;
    // new child to be checked
    child = parent*2;
    
    }
    
}

void heap_Sort(int a[], int last){
    int temp;
    while(last>1){
        temp = a[1];
        a[1] = a[last];
        a[last] = temp;
        last--;
        // heapify
       helper_maxheap(a, 1, last);
        
    }
}