1

Given an array containing N integers, your task is:

  • To create min-heap with 1 based indexing (Insert elements one by one).
  • Remove the element present at index k from the heap created in the first step using Decrease key method.
  • Print the updated heap after the second step.

I am failing a test case in particular

enter image description here

I am getting this as output

enter image description here

Here is my code

#include <bits/stdc++.h>
using namespace std;

void heapify(vector<int>&v, int idx, int last)
{
   int left = 2*idx;
   int right = left+1;
   int min_idx = idx;

   if(left<=last and v[min_idx]>v[left]) min_idx = left;
   if(right<=last and v[right]<v[min_idx]) min_idx = right;

   if(min_idx != idx)
   {
       swap(v[min_idx],v[idx]);
       heapify(v,min_idx,last);
   }

 }

 void build_min_heap(vector<int>&v)
 {
    int n = v.size()-1;

    for(int i=n/2; i>=0; i--) heapify(v,i,n);
 }

 void print(vector<int>v)
 {
     for(int i=0; i<v.size(); i++) cout<<v[i]<<" ";
     cout<<endl;
 }

 int main()
 {
     int t;
     cin>>t;

    while(t--)
    {
       int n,rm;
       cin>>n>>rm;

       vector<int>v;
       v.reserve(n);

       for(int i=0; i<n; i++) 
       {
           int k;
           cin>>k;
           v.push_back(k);
       }

       build_min_heap(v);
       v.erase(v.begin()-1+rm);
       build_min_heap(v);
       print(v);
  }

   return 0;
 }
underscore_d
  • 6,309
  • 3
  • 38
  • 64
  • Just looking at your code, consider the values of `min_idx` and `left` when the input argument `idx` travels all the way to zero, as the for-loop in `build_min_heap` allows. That looks... odd. E.g. What happens when `heapify(v, 0, (v.size()-1))` is invoked. Walk through that on paper. – WhozCraig Sep 01 '20 at 20:55
  • Not 100% sure but, maybe, Google is your friend: https://stackoverflow.com/q/17009056/10871073 – Adrian Mole Sep 01 '20 at 20:57
  • Side note: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – Werner Henze Sep 01 '20 at 21:03

0 Answers0