Heap Sort

Easy
0/40
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
AdobeExpedia GroupAmazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
4 
10 7 8 11
Sample Output 1:
7 8 10 11
Explanation Of Sample Input 1:
For the first test case, the array [10,7,8,11] will be converted into [7,8,10,11] after arranging into non-decreasing order.
Sample Input 2:
1
5
5 -2 3 -1 8
Sample Output 2:
-2 -1 3 5 8
Explanation Of Sample Input 2:
For the first test case, the array [5,-2,3,-1,8] will be converted into [-2,-1,3,5,8] after arranging into non-decreasing order.
Hint

Try to implement the entire heap sort algorithm.

Approaches (1)
Heap Sort

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].

 

Time Complexity

O(N * log(N)), where N is the size of ‘ARR’.

 

Since the Heapification take order of O(log(N)) time and we are applying Heapification N times, therefore the time complexity is of the order of O(N*log(N)).

Space Complexity

O(1).

 

Since we are using constant extra space the space complexity is O(1).

Code Solution
(100% EXP penalty)
Heap Sort
Full screen
Console