Heap Sort

In this tutorial we will be learning about Heap sort algorithm.

About Heap Sort

In this sorting algorithm we first build a heap using the given elements.

If we want to sort the elements in ascending order we create a
 Min Heap. And to sort the elements in descending order we create a 
Max Heap.

Once the heap is created we delete the root node from the heap and put the last node in the root position and repeat the steps till we have covered all the elements.

C Code

In this example we are sorting the elements in ascending order. We are saving element from index 1. So, index 0 is set to -1.

#include <stdio.h>

void display(int arr[], int size);
void heapSort(int arr[], int size);
void minHeap(int arr[], int size);

int main() {
  //unsorted elements
  //we are saving elements from index 1
  //so, index 0 is set to -1
  int arr[] = {-1, 40,60,10,20,50,30};

  //size of the array
  int n = sizeof(arr)/sizeof(arr[0]);

  //output unsorted elements
  display(arr, n);

  //sort the elements
  heapSort(arr, n);

  //display sorted elements
  display(arr, n);

  return 0;
}

void display(int arr[], int size) {
  int i;
  for(i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void heapSort(int arr[], int size) {
  //variables
  int i, j, tmp, sorted[size];
  sorted[0] = -1;  //index 0 is not used so set to -1

  //sort
  for(i = size , j = 1; i >= 1; i--, j++) {
    minHeap(arr, i);
    sorted[j] = arr[1];
    arr[1] = arr[i - 1];  //put last element to root node
  }

  //set the result
  for(i = 0; i < size; i++) {
    arr[i] = sorted[i];
  }
}

void minHeap(int arr[], int size) {
  int i, left, right, tmp, val;

  for(i = size / 2; i >= 1; i--) {

    //taking 1 as the start index
    //if parent node = i
    //so left child = 2i
    //and right child = 2i+1
    tmp = i;
    left = (2 * i);
    right = (2 * i) + 1;

    if(left < size && arr[left] < arr[tmp]) {
      tmp = left;
    }

    if(right < size && arr[right] < arr[tmp]) {
      tmp = right;
    }

    if(tmp != i) {
      val = arr[i];
      arr[i] = arr[tmp];
      arr[tmp] = val;
      minHeap(arr, size);
    }
  }
}