In 1964, heap sort was invented by John Williams.
Heap sort is a comparison-based sorting method.
First, we follow the rules of heap and keep the maximum value on the root if we are making a max heap, then we delete and store the root value and make that tree-like structure heap again, and when the maximum value is on the root again, we delete and store the root again, and this process is done until the array is over.
In the storage, the maximum value gets the highest position because it is deleted first, and the minimum value gets the lowest position because it is deleted last.
Let’s say this is the Max-heap
Now, to extract or store the elements in a sorted order, we have to delete the root until the tree is vanished.
if you want to visualize Heap Sort, then Click here
Max-heapify(a, i)
Left <– a[2i]
Right <– a[2i+1]
If (Left ≤ size of array && a[left] > root a[i])
  Largest_no <– left
Else
  Largest_no <– i
If Right ≤ size of array && a[Right] > a[Largest_no]
  Largest_no <– Right
If  Largest_no ≠root i
  Swap(a[i], Largest_no)
  Max-heapify(a, Largest_no)
Â
Size of array <– a[].length
int i;
for(i = a[].length/2; i ≥ 1; i–)
   max-heapify(a[], i)Â
Â
Build a max-heap(a[])
for i <– a[].length to 2
   Swap a[1] to a[i]
Â
Program of Heap Sort in C
Â
Time & Space Complexity of Heap Sort
In Best Case, time complexity is O(n).
For example – if input array is
Then, we need not heapify it after the last element deletes because this tree elements are identical.
So, swapping action performs n time + deletion operation performs n time, it means the time complexity is 2n. After we remove all constants, it is O(n).
Â
In Average case, time complexity is O(nlogn).
We perform the deletion of a root and heapify the tree into a max-heap or min-heap in ‘log n’ time.
Suppose there are n nodes in a max-heap.
(i) The deletion of root and heapify the tree will take logn time.
(ii) Then, heap contains n-1 nodes, so the deletion of the second node and heapify tree will take log(n-1) time.
(iii) Then, heap contains n-2 nodes, so the deletion of the third node and heapify tree will take log(n-2) time.
(iv) After performing n-2 deletions, the second last item will take log 2 time.
(v) After performing n-1 deletions, the last item will take O(1) time.
-> Sum of all operations = log(n) + log(n-1) + log(n-2) + … + log2 + 1 = log(n!) = n*log(n) – n + log(n)
-> The time complexity is after taking higher order term is O(n*log(n)).
Â
In Worst-Case, time complexity is O(nlogn).
Worst case input has all distinct elements. We place the elements in the heap in such a way that after every deletion, we use heapify function to rebuild the heap.
We perform same calculations as we do in the average case, and our operations are somewhat higher than average.
Â
   4. Space Complexity of heap sort is O(1).
Â
Test Yourself
Q1- Explain the basic concept of heap sort.
Heap sort is a comparison-based sorting algorithm that uses the concept of a binary heap to arrange elements in a tree-like structure. It maintains a max-heap (for ascending order) or min-heap (for descending order) property, where the root node contains the maximum or minimum value, respectively. During the sorting process, the maximum (or minimum) element is repeatedly extracted from the heap, and the heap is updated to maintain the heap property. This process continues until all elements are sorted.
Q2- Describe the steps involved in building a max-heap from an input array using the bottom-to-top heapify operation.
To build a max-heap using bottom-to-top heapify:
- Start from the last non-leaf node (index n/2 – 1) of the input array.
- Apply the max-heapify operation on each non-leaf node, which compares the node with its children and swaps if necessary to maintain the max-heap property.
- Continue this process for each non-leaf node, moving upwards towards the root.
- After all non-leaf nodes are heapified, the array will represent a valid max-heap.
Q3- How does heap sort handle duplicate elements during the sorting process?
Heap sort handles duplicate elements without any issues. The heapify operation compares the values of nodes during the sorting process, but it doesn’t differentiate between duplicate elements. When duplicate elements are present, they will be treated the same way during heapify, and the sorting will correctly handle their positions in the final sorted array.
Q4- Discuss the advantages and disadvantages of using heap sort as a sorting algorithm.
Advantages of heap sort
– Heap sort has a stable time complexity of O(n log n) in average and worst cases, making it efficient for large datasets.
– It is an in-place sorting algorithm, meaning it doesn’t require additional memory for sorting.
– Heap sort guarantees both stability and adaptability, which means it retains the relative order of duplicate elements and performs well on partially sorted data.
Â
Disadvantages of heap sort
– The constant factors involved in heap sort can make it slower in practice than other algorithms like quicksort or mergesort for smaller datasets.
– It has a space complexity of O(1), but the cache performance may not be as good as in other algorithms due to random access patterns.
Q5- Who invented heap sort?
Donald Knuth
John Williams
Alan Turing
John von Neumann
Ans – (2)
Explanation – Heap sort was invented by John Williams in 1964.
Q6- What is the time complexity of heap sort in the average case?
O(1)
O(n)
O(nlogn)
O(n^2)
Ans – (3)
Explanation – The time complexity of heap sort in the average case is O(nlogn).
Q7- During heap sort, which value is kept at the root node of a max heap?
Maximum value
Minimum value
Middle value
Average value
Maximum Value
Ans – (4)
Explanation – In a max heap, the maximum value is kept at the root node.
Q8- In the best case, when is heap sort time complexity O(n)?
When the input array is empty.
When the input array is already sorted.
When the input array contains duplicate elements.
When the input array contains only one element.
Ans – (2)
Explanation – In the best case, when the input array is already sorted, heap sort’s time complexity is O(n).
Q9- What is the worst-case time complexity of heap sort?
O(1)
O(n)
O(nlogn)
O(n2)
Ans – (3)
Explanation- The worst-case time complexity of heap sort is O(nlogn) when the input has all distinct elements.
Q10- Is heap sort an in-place sorting algorithm?
Yes, it requires additional memory for sorting.
No, it doesn’t require additional memory for sorting.
It depends on the input data.
It depends on the heap size.
Ans – (2)
Explanation- Heap sort is an in-place sorting algorithm as it performs sorting operations directly on the input array without requiring additional memory.
