For any queries you can reach us at / WhatsApp us: +919158876092

Heap Sort in Data Structures - Infovistar

Heap Sort

With heap sort, the elements are created using the min-heap and max-heap based on the elements of the given array.

In a min-heap or max-heap, the root element represents the minimum or maximum element of the array.

The heap sort recursively performs two main operations -

  • Create a heap H with the elements of the array.
  • Delete the root element of the heap formed in the first phase repeatedly.

What is a Heap?

A heap is a complete binary tree, and a binary tree is a tree in which a node can have utmost two children.

Complete binary trees are trees in which all the levels except for the last one, i.e., the leaf node, are completely filled and all the nodes are left-justified.

What is a Heap sort?

Heapsort is an efficient and popular sorting algorithm.

Heap sort involves removing the elements one by one from the heap part of the list.

Then, insert the elements into the sorted portion of the list.

Time Complexity

Case Time Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n log n)
  • Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
  • Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.
  • Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

Space Complexity O(1)
Stable No
  • The space complexity of heap sort is O (1).

Shell Sort