#### Concepts Used:

Heap

#### Difficulty Level:

Easy

#### Problem Statement :

Given an array containing N integers, our task is to create a min-heap using the elements of the given array and sort the array in descending order using heap sort.

**See original problem statement here**

#### Solution Approach :

#### Introduction :

Idea is to create a

min-heapthen replace the root with the last element. Now that the least valued element is stored at the last position, we willheapifythe remaining elements (or node) & repeat the process for all elements.

#### Method 1:

Sort the array in increasing order using any sorting algoritm which can be learnt from some online coding courses, now print the array staring from the last position (reverse order).

#### Method 2 :

In a

min-heap, the root always stores the smaller value as compared to itsleft&rightsubtree, this condition needs to be true for every node. We need to insert each item one by one such that it’s parent is always smaller than the item itself. If the parent is greater, then we need to swap the current item with its parent.In order to sort this

min-heapin decreasing order, we need to replace the root value with the last value and fix its position and performheapifywith the remaining nodes which are not fixed.

We will repeat this process untill all nodes are fixed.

#### Algorithms :

Insert():

- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
`2`

and repeat untill we reach root (first element).

**Heap Sort()**:

- Replace the root node with the farthest right node (last element).
- Fix the last node position and perform heapify with the remaining nodes.
- Repeat untill each node is fixed.

#### Heapify ():

- if the heap property holds true then you are done.
- else if
- the replacement node value <= its parent nodes value

then swap them, and repeat step 3.- else
- swap the replacement node with the smallest child node, and

repeat step 3.

#### Solutions:

[TABS_R id=1560]

[forminator_quiz id=”1566″]