Heap Sort Program in C

Introduction to Heap Sort in C

Heap sort in C is a sorting technique that uses a comparison technique and is based on a Binary heap data structure. Similar to that of the selection sort where the first minimum element is found and placed at the beginning and the process is repeated for other elements. The concept of heap sort is to eliminate the elements one by one from the heap list and insert them into the sorted part of the list. It is also called an in-place sorting algorithm.

Algorithm of Heap Sort in C

Following are the steps for the heap sort algorithm:

• From input data, build the max heap
• Since the maximum element is stored at the root of the heap, replace it with the element that is at the last in the heap and decrease the size of the heap by one.
• Heapify the root of the tree
• Repeat the steps given as long as the size of the heap is greater than one.

Illustration

What is Min Heap?

If the key at the root node is less than or equal to the keys present at the children node then the heap is called a min-heap.

What is Max Heap?

If the key at the root node is greater than or equal to the keys present at the children node then the heap is called a min-heap.

What is Heapify?

It is a process of creating a data structure called a heap from that of a binary tree using a data structure array.

Since in this, the loop runs from 2 to 0, at i=2, the function heapify is called and the elements are swapped.

At i=1, it checks the value at indexes 1. Since it is already in proper order, the tree is already heapified.

At i=0, the value at index 0 and 1 is checked. Since they are not in proper order, the elements are swapped. This iteration goes on until the elements are in proper order.

From this diagram, we start heapifying the smallest lower tree and move up gradually util we reach the element on the root.

Working of Heap Sort in C

• Since the property of the max heap is satisfied by the tree, the largest element of the tree is stored at the root node.
• Swap: the root element is removed and is put at the end of an array i.e nth position while the last element of the tree is put at the vacant place.
• Remove: the element is removed and the size of a heap is reduced to one.
• Heapify: the root element is heapified again so that the highest element is at the root.
• The process is repeated until all the elements in list are sorted.

Example of Heap Sort in C

Enter Elements in array:

16 21 40 3 2 5 9 18 17 16

Array After Heap Sort:

2 3 5 9 16 16 17 18 21 40

Program for Heap Sort with Implementation

Problem Description

Implement a heap sort program in c by using heapify method.

Syntax

Example

Output

Explanation

In this, the array is transformed into min heap. First, we iterate through the loop and compare the elements. If the elements are not in proper order then they are swapped. This process happens until all the elements are in their correct order.

Program to Sort an Array Using Heap Sort Algorithm

Output

Explanation

In this, the array heap is used for storing the values taken from the user. The array of max heap is created. The array is divided into two halves and both the sides of array are sorted. Once both the sides are sorted, the whole array is taken into consideration and the elements are swapped if not in correct order.

Complexity Heap Sort in C

The time complexity of heap sort is O(nlogn) considering all the case. The reason for this is that the height of the binary tree containing n elements is log n. In worst case, the root element needs to move to the last index making n swaps and hence nlogn.

Advantages and Disadvantages of Heap Sort Program in C

Advantages

• Memory usage- The usage of memory is minimal since only an array is needed for storing the elements taken from the user. No extra space is required.
• Efficiency- It is the time that is required to perform heap sort. It increases logarithmic as the number of elements increases.
• Simplicity - The algorithm is easy to understand since it does not include any complex functions like recursion.

Disadvantages

• It is slower as compared to quick sort because of the locality reference.
• It is lengthy to implement.

Applications of Heap Sort in C

• Used in algorithms like IntroSort
• K-sorted or k-largest element
• Used for security of embedded systems like linux kernel