Be the first user to complete this post

  • 0
 Add to List
Medium

328. Heap Sort

What is Heap Sort??

  • Heap sort is comparison based sorting algorithm.
  • Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region.
  • The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity.

Pre-requisite:

Binary Heap (min and max heap)

What is Binary Heap??

Heap is a tree based data structure which satisfies the two properties

Shape Property: Heap data structure is always a Complete Binary Tree. The Complete Binary tree is a binary tree which is completely filled (means all the nodes has 2 children) except the last level which might not be completely full.

Heap Property: All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes. This is called heap property.

 How Heap Sort Algorithm works???

  • Sorting in ascending order:
    1. Create a max Heap from the given input array.
    2. Extract the root (it will be the maximum value in array) and replace it with the last element in the array.
    3. Heapify the root of the heap.
    4. Repeat the steps b and c till entire array is sorted.
  • Sorting in descending order
    1. Create a min Heap from the given input array.
    2. Extract the root (it will be the minimum value in array) and replace it with the last element in the array.
    3. Heapify the root of the heap.
    4. Repeat the steps b and c till entire array is sorted.

Time Complexity: O(nLogn)

See the video below for more understanding

Output:

Original array is: [9, 10, 5, 3, 1, 2, 6]
Sorted array is (Heap Sort): [1, 2, 3, 5, 6, 9, 10]

Related Problems: