Heap Sort in C

In this tutorial, we will learn about heap sorting in C language, but before going to Heap sort, we have to know the concept of Complete Binary Tree.

What is Complete Binary Tree:

When each node in a tree in Data Structure has a maximum of two child nodes, then we call the tree a Binary tree.

A complete binary tree is nothing but a binary tree in which every level is filled completely, except the lowest one, which is filled from the left.

Binary Heap:

A Binary Heap is a specific kind of complete binary tree in which the elements are stored in a unique way or in a unique order such that the value recorded in the parent node must be more than or less than the values of the two children’s nodes.

Type of Heap:

Following are the two types of heap:

1. Max Heap
2. Min Heap

1. Min Heap:

When the parent node of a heap is smaller than the child node, the heap is said to be a min heap.

2. Max Heap:

A heap is said to be a Max heap if each parent node is higher than each child node.

Relationship between Tree Elements and Array Indexes:

The array is a simple way to represent a binary tree, and it uses very little space to do so.

Imagine that in the representation of the array, the parent node has index I, the left child node has index 2*I+1, and the right child node has index 2*I+2 (This indexing follows the zero-based indexing rule).

So, we may conclude that the heap is essentially a tree-based data structure, with the tree being primarily a complete binary tree. We can state that the height of the binary tree will be log n if a complete binary tree has n nodes. This data structure is very useful for eliminating the higher or the lower priority element.

Max Heap and Min Heap differ in the following ways:

Max Heap	Min Heap
The root node's key exceeds or is equal to the child nodes' keys in the tree.	The key located at the root node of the tree is smaller than or equal to the keys located at its child nodes..
The descending attribute is used by Max-Heap.	The ascending attribute is used by Min-Heap.
The root of a Max-Heap contains the maximal key element.	The smallest key element is found at the root of a Min-Heap.
A Max-Heap is constructed with the largest component coming first.	A Min-Heap is built with the smallest component placed first.
From the heap, largest element is popped out as the first element.	From the heap, smallest element is popped out as the first element.

"Heapify" Means:

The process used to change a binary tree into a heap data structure is called “heapify”. A binary tree may only contain two child nodes. Only the node whose children nodes are heapified is capable of undergoing the heapify procedure.

A complete binary tree is required for a heap. Starting with a complete binary tree, the heap can be transformed into a Max-Heap by using the function "heapify" on all of its non-leaf components. The heapify algorithm uses recursion.

Heap Sort:

• The divide and conquer technique are used in heap sort, just like it is in selection sort. It builds the subarrays and compares them to produce an ordered list that may be ascending or descending.
• To hold the elements of the array in heap sort, we utilise a heap tree data structure. The child element is compared to its parent element using the heap tree, and a swap is made if necessary.
• Using the max heap structure or the min heap structure is one of our two alternatives for heap sorting.
• When using the max heap, we attempt to retrieve the largest element from the root node. The goal of the min heap is to eliminate the root node's smallest element. For both the first and last index values, we can determine the element. We frequently implement the heap sort using the max heap structure.

How Heap Works:

• Consider the array to be a heap tree, with the child nodes of each element being on the (2*i+1) and (2*i+2) indices.
• Create the maximum heap for each sub-tree using the heapify function, then repeatedly remove the element with the largest value from the heap and insert it into the array.

Algorithm of Heap Sort:

heapSort(array)  
BuildMaxHeap(array)  
for index = length(array) to 2  
    swap arr[1] with array[index]  
        heap_size[array] = heap_size[array] ? 1  
        MaxHeapify(array,1)  
End

BuildMaxHeap(array

1.	BuildMaxHeap(arr)  
2.	heap_size(array) = length(array)  
3.	for index = length(array)/2 to 1  
4.	MaxHeapify(array,index)  
5.	End  

MaxHeapify(array,index)

1.	MaxHeapify(array,index)  
2.	Lef = left(index)  
3.	Ri = right(index)  
4.	if Lef ? heap_size[array] and array[Lef] > array[index]  
5.	largest = Lef  
6.	else  
7.	largest = index  
8.	if Ri ? heap_size[array] and array[Ri] > array[largest]  
9.	largest = Ri  
10.	if largest != index  
11.	swap array[index] with array[largest]  
12.	MaxHeapify(array,largest)  
13.	End   

Explaining the Algorithm:

Let's now see an illustration of the heap sort algorithm.

1. We'll start by asking the user to submit an array that needs to be sorted.
2. As soon as the array is received, a heap must be created so that the elements can be sorted in ascending order.
3. It is now necessary to generate a max heap from the heap. The value of the root node, or parent node, is always greater than or equal to the value of the child nodes, which is a key concept to remember.
4. The above requirement must be verified following tree construction. If the child node's value is higher than the parent node's, the procedure must be repeated until the max-heap property is satisfied.
5. The root node must be switched with the last node once all requirements have been met.
6. We can now remove the last node from our heap because it has been sorted.
7. The first three steps (Steps 4,5, & 6) must be performed until there is only one element remaining in the heap.

Implementation of Heap Sort:

C Program to sort the given elements using Heap Sort

// Heap Sort in C
#include <stdio.h>
// Function for swapping the position of two elements
void swap(int *a, int *b) {
  int tem = *a;
  *a = *b;
  *b = tem;
}
void heapify(int array[], int num, int index) {
  // Find the largest element among root, left child, and right child
  int max = index;
  // l is the left child
  int l = 2 * index + 1;
  // r is the right child
  int r = 2 * index + 2;
  if (l < num && array[l] > array[max])
    max= l;
  if (r < num && array[r] > array[max])
    max= r;
  // Swap and continue heapifying if the root is not the largest
  if (max!= index) {
    swap(&array[index], &array[max]);
    heapify(array, num, max);
  }
}
// Main function of heap sort
void heapSort(int array[], int num) {
  // Building max heap
  for (int index = num / 2 - 1; index >= 0; index--)
    heapify(array, num, index);
  // Heap sort
  for (int index = num - 1; index >= 0; index--) {
    swap(&array[0], &array[index]);
    // Heapify the root element to get the highest element at root again
    heapify(array, index, 0);
  }
}
//To print the array
void printArray(int array[], int num) {
  for (int index = 0; index < num; index++)
    printf("%d ", array[index]);
  printf("\n");
}
//Main code
int main() {
  int arr[] = {62,94,19,48,37,52,9};
  int n = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, n);
  printf("The sorted array is -\n");
  printArray(arr, n);
  return 0;
}

Output:

The sorted array is -
9 19 37 48 52 62 94

Heap Sort Operations

1. As a result of the tree satisfying the Max-Heap property, the largest item is kept at the root node.
2. Swap: Take off the array's root element and add it at the end (nth position) Place the last component of the tree (heap) in the empty space.
3. Remove: Reduce the heap's size by 1.
4. Heapify: Reheapify the root element so that it is at the root position and is the highest element.

The procedure is carried out once again until the entire list of things is sorted.

The Uses of Heap Sort

• Heap Sort is a technique that can be used for embedded devices and systems like the Linux Kernel that are concerned with security.
• This method also aids in quickly identifying the smallest or largest element from a data structure. Additionally, we may utilise Heap Sort to handle the priority queues in the prim algorithm as well as to determine the order in statistics.
• Although heap sort has a lower worst-case time complexity than other sorting algorithms like merge sort, quick sort, etc., it is not widely used.

Complexity of Heap Sort:

Time Complexity
Worst Case	O(n logn)
Average Case	O(n logn)
Best Case	O(n logn)

Space Complexity

O(1)

• For all circumstances, Heap Sort has O(nlog n) time complexity ( best case, average case, and worst case).
  
  Let's analyse why a complete binary tree with n items has a height of log n.

• When the subtrees of an element are max-heaps, we must continue to compare the element with its left and right children and push the element down until both of its children are smaller than it in order to fully heapify the element.
• In the worst scenario, moving one element from the root to the leaf node will require multiples of log(n) comparisons and swaps.
• Since we do this for n/2 elements during the build_max_heap stage, the worst-case complexity of the build heap phase is n/2*log ~ n nlog n.
• We heapify the root element after exchanging it with the last element during the sorting process. Again, this requires log n worst time for each element because we might need to move one element all the way from the root to the leaf. Given that we do this n times, the heap sort step likewise takes up nlog n.
• Additionally, because the heap sort and build max heap processes are carried out sequentially, the algorithmic complexity does not increase and stays in the order of nlog n.
• Additionally, it sorts data with an O(1) space complexity. Compared to Quick Sort, it has a better worst-case time (O(nlog n)). In the worst-case situation, the complexity of Quick Sort is O(n2). However, Quick Sort can be quick in some circumstances. Introsort is a heapsort substitute that maintains the advantages of both algorithms—the average performance of quicksort and the worst-case speed of heapsort.

Advantages of Heap Sort:

• Since the performance of the heap sort is so optimal and effective, it follows that no other sorting algorithm will perform more effectively than the heap sort in comparison.
• It doesn't require any additional space to operate other than what is required to hold the initial list of items to be sorted. So, it is safe to say that Heap Sort uses relatively little Memory space.
• Because it doesn't involve complex computer science ideas like recursion, the Heap Sort algorithm is much simpler to grasp than other effective sorting algorithms.

Disadvantages of Heap Sort:

• This sort is unstable and has the capacity to alter the relative hierarchy.
• The constant factors in heap sort are expensive. Even though the complexity of Quick Sort and Heap Sort is the same (O(nlogn)), partitioning is quicker than heap maintenance.
• Heap Sort is not recommended when dealing with big datasets, although Merge Sort performs better in this situation.

Conclusion:

Heap Sort and its ideas are covered in-depth in the article. We also covered the relationship between array indexes and tree elements, heap data structures, and heap types. We learned about heap sort's time and space complexity as well as heapify and its uses. Additionally, we learned how to implement the heap sort algorithm and how it functions.