C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++

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.



ADVERTISEMENT
ADVERTISEMENT