C Program for Heap Sort
Heap sort is a comparison-based sorting technique. It works on the data structure known as “the binary heap”. It is one of the most efficient sorting algorithms. It takes relatively less time than selection sort, bubble sort, and insertion sort. Heap sort is an unstable sorting algorithm since the position of a similar element gets changed. Heap sort works with Max Heap (Heap is a complete binary tree. A max heap has a parent node greater than the child nodes).
In this article, we going to deep dive into the sorting algorithm and working of heap sort. We are also going to implement heap sort in C language.
Heap Sort Algorithm
Step 1 : Create a MaxHeap function. This function will change the given array data to the max heap.
Step 2 : Swap the root node(the largest element) with the last element. Then heapify the root node of the current tree to maintain the property of Max Heap.
Step 3 : Repeat Step 2 until the max heap becomes empty. Place the element in the correct position.
Step 4 : Repeat Step 2 and Step 3 until every element of the array is the correct sport.
Step 5 : End
Heapify Method (Algorithm)
Step 1 : Compare the value at the current node(index i) with its left child (indexed at 2*i + 1) and its right child (indexed at 2*i + 2), if they exist.
Step 2 : Find the largest of current node, left child and right child.
Step 3 : Swap the largest of all with the current node( if needed).
Step 4 : If a swap was done, make sure the subtree that was rooted at the index where the highest value was found also meets the max-heap property by recursively applying the heapify() to it.
Example of the Heap Sort
Step 1: Array Input Taken and then inserting the elements in a Binary Tree.
Step 2: Using Max Heapify to get the maximum element at the top.
Step 3: Removing the element from the Binary Tree and then adding the element in result array(Maximum element).
Step 4: Continue the above step to get the second top element. Continue it till Tree is Empty.
Step 5: After Removing all the elements we get the sorted Array created using the removed elements.
Program For Heap Sort
Below is the implementation of the above method:
C
// C Program for HeapSort #include <stdio.h> // Heapify function void heapify( int arr[], int n, int i) { int temp, maximum, left_index, right_index; // currently assuming i postion to // be holding the largest value maximum = i; // right child index right_index = 2 * i + 2; // left child index left_index = 2 * i + 1; // if left index value is grater than the current index // value if (left_index < n && arr[left_index] > arr[maximum]) maximum = left_index; // if right index value is grater than the current index // value if (right_index < n && arr[right_index] > arr[maximum]) maximum = right_index; // checking if we needed swaping the elements or not if (maximum != i) { temp = arr[i]; arr[i] = arr[maximum]; arr[maximum] = temp; heapify(arr, n, maximum); } } // HeapSorting function void heapsort( int arr[], int n) { int i, temp; // performing heapify on the non leaf nodes so n/2 - 1 // to 0 are the non leaf nodes for (i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // the current array is changed to max heap for (i = n - 1; i > 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } // Driver code int main() { // initializing the array int arr[] = { 20, 18, 5, 15, 3, 2 }; int n = 6; // Displaying original array printf ( "Original Array : " ); for ( int i = 0; i < n; i++) { printf ( "%d " , arr[i]); } printf ( "\n" ); heapsort(arr, n); // Displaying sorted array printf ( "Array after performing heap sort: " ); for ( int i = 0; i < n; i++) { printf ( "%d " , arr[i]); } return 0; } |
Original Array : 20 18 5 15 3 2 Array after performing heap sort: 2 3 5 15 18 20
Complexity of the Above Method:
Time complexity: O(n*log n), where ‘n’ is number of elements in the array.
Auxiliary Space: O(1)
Contact Us