Deleting ith index in minimum heap

Question

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
        }
     }
  }
}

*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* -- You don't know a concept, yet you wrote a program implementing a concept you want explained. Confusing... — PaulMcKenzie, Aug 14 '17 at 14:37
@PaulMcKenzie thanks for appreciating my efforts. Yeah, I am still learning. and when I am done with this code, I will let you know :) — Xandie, Aug 14 '17 at 16:26
what is the sample input you tried and how did you reach to conclusion it didn't work — Hariom Singh, Aug 17 '17 at 03:30

score 1 · Answer 1 · answered Aug 23 '17 at 12:35

1

This is the most beautiful explanation I came through while strolling. Seekers, take a look!

answered Aug 23 '17 at 12:35

Xandie

31
6

Link-only answers are discouraged. The link might become stale. You should consider adding text that outlines the solution, and provide the link as the source, so that others can visit it if they need to. – Jim Mischel Aug 24 '17 at 14:32

score 0 · Answer 2 · answered Aug 16 '17 at 11:05

0

Here a really good solution is available. Just check the delete operation of min heap.

http://www.geeksforgeeks.org/binary-heap/

answered Aug 16 '17 at 11:05

nagendra547

5,672
3
29
43

what was the bug you found? – Hariom Singh Aug 17 '17 at 03:29
Actually, there were few cases which my algorithm wasn't able to handle. I found an amazing explaination & it worked beautifully. – Xandie Aug 23 '17 at 12:33
That's not the best way to do it. See my link in comments. – Jim Mischel Aug 24 '17 at 20:16

Deleting ith index in minimum heap

2 Answers2