{"id":1544,"date":"2020-07-01T09:30:38","date_gmt":"2020-07-01T09:30:38","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1544"},"modified":"2022-03-23T23:08:09","modified_gmt":"2022-03-23T23:08:09","slug":"heap-sort","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/heap-sort\/","title":{"rendered":"Heap Sort"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Heap<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to create a min-heap<\/strong> then replace the root with the last element. Now that the least valued element is stored at the last position, we will heapify<\/strong> the remaining elements (or node) & repeat the process for all elements.<\/p>\n<\/blockquote>\n

Method 1:<\/h4>\n
\n

Sort the array in increasing order using any sorting algoritm, now print the array staring from the last position (reverse order).<\/p>\n<\/blockquote>\n

Method 2 :<\/h4>\n
\n

In a min-heap<\/strong>, the root always stores the smaller value as compared to its left<\/strong> & right<\/strong> 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. <\/p>\n

In order to sort this min-heap<\/strong> in decreasing order, we need to replace the root value with the last value and fix its position and perform heapify<\/strong> with the remaining nodes which are not fixed.
\nWe will repeat this process untill all nodes are fixed.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Algorithms :<\/h3>\n

Insert()<\/strong> :<\/h4>\n
\n
    \n
  1. Insert the item at the last index, and increment the size by 1.<\/li>\n
  2. Then, check if the inserted item is smaller than its parent,<\/li>\n
  3. If yes, then swap the inserted item with its parent.<\/li>\n
  4. If no, then do nothing.<\/li>\n
  5. Now, go to step 2<\/code> and repeat untill we reach root (first element).<\/li>\n<\/ol>\n<\/blockquote>\n

    Heap Sort()<\/strong>:<\/h4>\n
    \n
      \n
    1. Replace the root node with the farthest right node (last element).<\/li>\n
    2. Fix the last node position and perform heapify with the remaining nodes.<\/li>\n
    3. Repeat untill each node is fixed.<\/li>\n<\/ol>\n<\/blockquote>\n

      Heapify ():<\/h4>\n
      \n
        \n
      1. if the heap property holds true then you are done.<\/li>\n
      2. else if<\/li>\n
      3. the replacement node value <= its parent nodes value
        \nthen swap them, and repeat step 3.<\/li>\n
      4. else<\/li>\n
      5. swap the replacement node with the smallest child node, and
        \nrepeat step 3.<\/li>\n<\/ol>\n<\/blockquote>\n

        Solutions:<\/h3>\n\t\t\t\t\t\t