Heap Sort

Heap sort is a comparison-based sorting algorithm that utilizes the heap data structure to arrange elements in a particular order. It is an in-place algorithm, meaning it doesn’t require additional data structures to perform the sorting operation.

Here is the detailed explanation of Heap Sort:

• It uses the concepts of max-heap and min-heap, where in max-heap, the largest element is the root node, and in min-heap, the smallest element is the root node.
• Heap sort is a comparison-based sorting algorithm that sorts an array by creating a binary heap data structure. It has an average and worst-case time complexity of O(n log n)

Advantages of Heap Sort:

• Efficient: Heap sort has a time complexity of O(nlogn), making it one of the most efficient sorting algorithms.
• In-Place Sorting: Heap sort is an in-place sorting algorithm, which means it sorts the elements within the input array without using any extra memory. This makes it more memory-efficient than other sorting algorithms like quicksort and merge sort.
• Stable Sorting: Heap sort is a stable sorting algorithm, which means that the relative order of elements with equal values is preserved. This is important in many applications where the elements are records with multiple fields and the sorting is based on multiple criteria.
• Easy to Implement: Heap sort is easy to implement and understand, making it a good choice for students and beginners who are learning data structures and algorithms.

Disadvantages of Heap Sort:

• Not the Fastest: Although heap sort is efficient, it is not the fastest sorting algorithm. Quicksort and merge sort are generally faster than heap sort in practice.
• Not Adaptive: Heap sort is not adaptive, which means it does not perform well on partially sorted arrays or arrays with many repeated values. In these cases, quicksort is a better choice.
• Space Complexity: Although heap sort is an in-place sorting algorithm, its space complexity is O(1), which is the same as other sorting algorithms like quicksort and merge sort. However, it is important to note that the space complexity of an algorithm refers to the amount of extra memory used by the algorithm and not the amount of memory used by the input data.

What is Heapify?

→Heapify is the process of converting a binary tree into a valid heap data structure. This is usually achieved by starting from the last internal node and working towards the root node, swapping the node with its largest child node until the heap property is satisfied. The process is repeated for the affected subtrees until the entire tree is a valid heap. The time complexity of heapify is O(log n), where n is the number of nodes in the tree.

Heap Sort Algorithm:

1. First convert the array into heap data structure using heapify, then one by one delete the root node of the Max-heap and replace it with the last node in the heap and then heapify the root of the heap. Repeat this process until size of heap is greater than 1
2. Build a heap from the given input array.
3. Repeat the following steps until the heap contains only one element:
4. Swap the root element of the heap (which is the largest element) with the last element of the heap.
5. Remove the last element of the heap (which is now in the correct position).
6. Heapify the remaining elements of the heap.
7. The sorted array is obtained by reversing the order of the elements in the input array.

Working of Heap sort Algorithm:

Let’s take an unsorted array:

Step 1:

First, we have to construct a heap from the given array and convert it into max heap.

Step 2:

Next, we have to delete the root element (89) from the max heap. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 3:

In the next step, again, we have to delete the root element (81) from the max heap. To delete this node, we have to swap it with the last node, i.e. (54). After deleting the root element, we again have to heapify it to convert it into max heap

Step 4:

In the next step, we have to delete the root element (76) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 5:

In the next step, again we have to delete the root element (54) from the max heap. To delete this node, we have to swap it with the last node, i.e. (14). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 6:

In the next step, again we have to delete the root element (22) from the max heap. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 7:

In the next step, again we have to delete the root element (14) from the max heap. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 8:

In the next step, again we have to delete the root element (11) from the max heap. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

Step 9:

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are :

Heap sort complexity

1. Time Complexity

2. Space Complexity