{"id":8561,"date":"2022-06-20T09:27:01","date_gmt":"2022-06-20T09:27:01","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=8561"},"modified":"2022-07-20T09:47:49","modified_gmt":"2022-07-20T09:47:49","slug":"heap-sort-for-decreasing-order-using-min-heap","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/heap-sort-for-decreasing-order-using-min-heap\/","title":{"rendered":"Heap Sort for decreasing order using min heap"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement:<\/h3>\n

In this problem, we have given an array, and we have to sort the array in decreasing order using a min-heap.<\/p>\n

Example:<\/em><\/strong><\/p>\n

Input : arr[] = {1, 50, 100, 25}
\nOutput : arr[] = {100, 50, 25, 1}<\/p>\n

What is Heap?<\/h3>\n

A heap is a complete binary tree, A complete binary tree is a binary tree in which all the levels are completely filled except the last level i.e. leaf node.<\/p>\n

What is a Heap Sort Algorithm?<\/h3>\n

Heap Sort is a popular sorting Algorithm that processes the element by creating the min-heap or max-heap using the given array. Min-heap or max-heap represents the ordering of the array; the value of the root element will represent the minimum or maximum element of the array.<\/p>\n

The basic concept of heap sort is to eliminate the elements one by one from the heap and then insert them in a sorted manner.<\/p>\n

How to \u201cheapify\u201d a tree?<\/h3>\n

So, we can modify the tree in the max heap or min-heap. In other words, we can say, The reshaping of a binary tree into a heap tree is called heapify.<\/p>\n

Min – Heap<\/strong> follows the property of a complete binary tree in which the value of the internal node is smaller than or equal to the value of the children of that node.
\nIn 0 – based indexing, the node stored at k index in the array will have its left child held at index 2k + 1 and its right child at index 2k + 2.<\/p>\n

\"\"<\/p>\n

Approach:<\/h3>\n
    \n
  • The idea is quite simple, we will build a min-heap of the given array.<\/li>\n
  • And, perform the heapify method on the tree.<\/li>\n
  • In heapify, we\u2019ll compare the root node with both the children.<\/li>\n
  • And perform the swap operation according to the min-heap condition.<\/li>\n<\/ul>\n

    Algorithm:<\/h3>\n
      \n
    • Build a min-heap from the given input array.<\/li>\n
    • After this, the smallest node is stored at the root of the heap. Replace it with the last node of the heap until the size of the heap gets 1.<\/li>\n
    • Heapify the root of the tree.<\/li>\n
    • Repeat the above steps while the size of the heap is greater than 1.<\/li>\n<\/ul>\n

      Dry Run:<\/h3>\n

      \"\"<\/p>\n

      Code Implementation<\/h3>\n\t\t\t\t\t\t