{"id":1466,"date":"2020-07-01T09:30:54","date_gmt":"2020-07-01T09:30:54","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1466"},"modified":"2022-03-23T06:52:55","modified_gmt":"2022-03-23T06:52:55","slug":"remove-kth-element-from-min-heap","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/remove-kth-element-from-min-heap\/","title":{"rendered":"Remove Kth element from Min Heap"},"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:<\/p>\n

    \n
  1. Create min-heap with 1 based indexing.<\/li>\n
  2. Remove the element present at index k from the heap created in the first step using Decrease key method.<\/li>\n
  3. Print the updated heap after second step.<\/li>\n<\/ol>\n<\/blockquote>\n

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

    Solution Approach :<\/h3>\n

    Introduction :<\/h4>\n
    \n

    Our task is pretty straight forward, we just need to perform two operations :<\/p>\n

      \n
    • Create a min-heap<\/strong>.<\/li>\n
    • Delete an element at given position k<\/code> with decreaseKey()<\/strong>.<\/li>\n<\/ul>\n<\/blockquote>\n

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

      We can use sorting algorithms to sort our array in increasing order, and delete kth<\/code> value of the array. Now print the remaining array.<\/p>\n<\/blockquote>\n

      Method 2(Using Heap) :<\/h4>\n
      \n
        \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<\/li>\n

      • \n

        In the deletion process, we can only delete any item if it is the root. So, first we need to take the item (to be deleted), in the root’s position then extract it (remove) using decreaseKey()<\/strong> and store the last item of the heap in the root and reduce the size of our heap by 1.<\/p>\n<\/li>\n

      • \n

        Since, now the last item is stored in the root’s place this might void the heap property. So, we need to heapify<\/strong> the last node placed at the position of root.<\/p>\n<\/li>\n

      • \n

        Below is the algorithm of above approach.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n

        Algorithms :<\/h3>\n

        Insert()<\/strong> :<\/p>\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

          decreaseKey()<\/strong>:<\/p>\n

          \n
            \n
          1. Take the index of the element to be removed.<\/li>\n
          2. Assign the least possible value in the index position.<\/li>\n
          3. Swap the value at this index untill it takes root’s position.<\/li>\n
          4. extract()<\/strong> it and call heapify()<\/strong> since we just removed a node and this might void the heap property.<\/li>\n<\/ol>\n<\/blockquote>\n

            Extract()<\/strong> :<\/p>\n

            \n
              \n
            1. Store the value of the first node of our heap ( temp = heap[0]<\/code> ).<\/li>\n
            2. Replace the root node with the farthest right node (last element). (heap[0] = heap[size-1])<\/code><\/li>\n
            3. Decrease the size by 1<\/code>.<\/li>\n
            4. Perform heapify<\/strong> starting from the new root. <\/li>\n
            5. Return the stored value (temp<\/code>).<\/li>\n<\/ol>\n<\/blockquote>\n

              Heapify()<\/strong>:<\/p>\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 > then 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

                Example:<\/h4>\n

                \"\"<\/p>\n

                Solutions:<\/h3>\n

                \t\t\t\t\t\t