c++ - 删除最小堆中的第i个索引

有人可以解释一下在由数组表示的min-heap中删除第i个元素的概念，并在删除操作后保留heap属性。

第i个节点的左子节点: 2*i + 1
第i个节点的右子节点: 2*i + 2
第i个节点的父节点: (i-1)/2
这就是我尝试过的方法，但这不能正确处理所有条件:

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

最佳答案

这里提供了一个非常好的解决方案。只需检查最小堆的删除操作即可。

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