Can someone please explain the concept for deleting the i-th element in the min-heap that is represented by an array and maintain the heap property after deletion operation.
Left child of i-th node: 2*i + 1
Right child of i-th node: 2*i + 2
Parent of i-th node: (i-1)/2
That's how I tried, but this doesn't handles all the conditions properly:
void deleteKey(int i)
{
if(i > capacity && i < 0) //capacity : max size of heap
return;
heap_size--; //current heap size
//swapping last & required elements
harr[heap_size] = harr[heap_size] ^ harr[i]; //harr[] : heap array
harr[i] = harr[heap_size] ^ harr[i];
harr[heap_size] = harr[heap_size] ^ harr[i];
int j = heap_size - 1;
while(2*i <= j)
{
if(left(i)<= j) //if there's only left node
{
if(right(i) <= j) //if there is right too
{
//finds index with min value
int x = harr[left(i)] < harr[right(i)] ? left(i) : right(i);
//swaps array elements
swap(&harr[x] , &harr[i]);
//updating current & required node
i = x;
}
else
{
swap(&harr[left(i)], &harr[i]);
i = left(i); //updating current & required node
}
}
}
}
