Heap Sort

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-heap then replace the root with the last element. Now that the least valued element is stored at the last position, we will heapify the 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 its left & right subtree, 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-heap in decreasing order, we need to replace the root value with the last value and fix its position and perform heapify with the remaining nodes which are not fixed.
We will repeat this process untill all nodes are fixed.

Algorithms :

Insert() :

  1. Insert the item at the last index, and increment the size by 1.
  2. Then, check if the inserted item is smaller than its parent,
  3. If yes, then swap the inserted item with its parent.
  4. If no, then do nothing.
  5. Now, go to step 2 and repeat untill we reach root (first element).

Heap Sort():

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

Heapify ():

  1. if the heap property holds true then you are done.
  2. else if
  3. the replacement node value <= its parent nodes value
    then swap them, and repeat step 3.
  4. else
  5. swap the replacement node with the smallest child node, and
    repeat step 3.

Solutions:

[TABS_R id=1560]

[forminator_quiz id=”1566″]

Previous post Minimum Difference
Next post Print first K non-repeating characters of a string

Leave a Reply

Your email address will not be published. Required fields are marked *