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
I am getting this as output
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;
}