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:

Create a max Heap from the given input array.

Extract the root (it will be the maximum value in array) and replace it with the last element in the array.

Heapify the root of the heap.

Repeat the steps b and c till entire array is sorted.

Sorting in descending order

Create a min Heap from the given input array.

Extract the root (it will be the minimum value in array) and replace it with the last element in the array.

Heapify the root of the heap.

Repeat the steps b and c till entire array is sorted.

Time Complexity: O(nLogn)

See the video below for more understanding

Complete Java Code for Heap Sort:

Output:

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

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________