Last Updated: 15 Mar, 2021
Heap Sort
Easy
Asked in companies
You are given an array ‘ARR’ consisting of 'N' integers, and your task is to sort the given array in non-decreasing order using the Heap sort algorithm.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains a single integer 'N', as described in the problem statement.
The second line of each test case contains 'N' space-separated integers, representing the elements of the array.
Output Format:
For each test case print 'N' space-separated integers arranged in non-decreasing order.
The output of every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
-10^9 <= ARR[i] <= 10^9
Where ‘T’ denotes the number of test cases and ‘N’ denotes the size of ‘ARR’.
Time Limit: 1sec
Approaches
Approach:
- Heapsort is a sorting algorithm based on the heap data structure.
- In this algorithm, we will first convert the given array into a max heap.
- The max heap is a special kind of binary tree with the following properties:
- It is a complete binary tree.
- The element present at the root node is the largest among all of its children.
- Since max heap is a complete binary tree, hence it can be converted into an array-based representation where if the parent node is present at index ‘i’, then its left and right children will be present at the index (2 * ‘i’ + 1) and (2 * ‘i’ + 2)(we are assuming 0-based indexing) respectively.
- We will be using the process of Heapification in which we convert the given array in such a way that it follows the property of a heap. i.e. in a max heap for every element present at the index ‘i’, it should be greater than both of its children present at the index (2 * ‘i’ + 1) and (2 * ‘i’ + 2).
- Now, we will convert the given array into a max heap and since the biggest element is present at the 0th index initially in a max heap, we will swap the first and the last element of the array and then again perform the Heapification process on the remaining array of size ‘N’ - 1. Therefore after each time we apply the Heapification process, the biggest element in the remaining array will be present at the 0th index and we will shift it to the last and hence after applying the Heapification process ‘N’ times the complete array will be arranged in non-decreasing order.
Example: let the given array is [5 2 1 3 12 8].
Similar problems