Heap Sort - C Implementation

Heap Sort - C Implementation

Tree is the most important and fundamental part of Computer Science. Trees can be used to build things, Parse things and interpret things, and we can even use them to sort things.

Ah Sorting! we have done so much of it in the past articles, but it will be unfair to stop our discussion on sorting without discussing Heap Sort.

So What Is A Heap?

Before going into Heap sort, it is necessary to understand what is heap. Heap is nothing more than just a binary tree with some additional rules that it has to follow.

1.) All the levels of binary tree must be filled from left to right.

2.) It should either be a max_heap or a min_heap. Here we'll be dealing with max_heap, where every parent node(be it root) must be greater than or equal to the value of its children.

Algorithm for Heap Sort

1.) We Start off with an unsorted array.

2.) We transform that unsorted array into a heap.

3.) Since we need a max heap in order to implement heap sort, we'll transform our heap into a max heap.

4.) Swap the root node with the last node; after we do this, the last node  will hold the largest(max value) item. So, it is considered sorted and we can remove it from the heap.

5.) We have one less node in our heap,but it is no longer a max heap! We'll need to move the elements in its correct place to make it max heap once again.

6.) Now that we have a max heap again, we can repeat the same steps.

---

#include <stdio.h> void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { int temp=arr[i]; arr[i]=arr[largest]; arr[largest]=temp; heapify(arr, n, largest); } } void heapSort(int arr[],int n) { for(int i=n/2-1;i>=0;i--) heapify(arr,n,i); for(int i=n-1;i>=0;i--) { int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; heapify(arr,i,0); } } void printArray(int arr[],int n) { for(int i=0;i<n;i++) printf("%d ",arr[i]); printf("\n"); } int main() { int arr[]={30,43,33,51,18,54,27}; int n=sizeof(arr)/sizeof(arr[0]); heapSort(arr,n); printf("Sorted Array is \n"); printArray(arr,n); }