为什么将删除元素从错误中删除的实现？

Question

如果知道要删除的元素的位置，则我对删除元素的删除元素的实现是：

void MinHeap::deleteKey(int i)
{
    if(heap_size>0 && i<heap_size && i>=0)
    {
        if(heap_size==1)
            heap_size--;
        else
        {
            harr[i] = harr[heap_size-1];
            heap_size--;
            if(i<heap_size)
                MinHeapify(i);
        }
    }
    return ;
}

Minheapify（）函数（）如下：

void MinHeap::MinHeapify(int i) 
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i]) smallest = l;
    if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        MinHeapify(smallest);
    }
}

Minheap的结构如下：

struct MinHeap
{
    int *harr;
    int capacity, heap_size;
    MinHeap(int cap) {heap_size = 0; capacity = cap; harr = new int[cap];}
    int extractMin();
    void deleteKey(int i);
    void insertKey(int k);
    int parent(int i);
    int left(int i);
    int right(int i);
};

删除的实现是遵循我们交换的逻辑的逻辑。要删除最后一个元素的元素（我只是在不需要删除元素时删除的元素上的最后一个元素），然后减小堆数组的大小。我们终于从已删除元素的位置（现在由最后一个元素占据）来缩小堆。 该实现适用于某些但不是所有测试用例。 这种方法有什么错误？

Answer 1

考虑以下最小堆：

       0
      / \
     4   1
    / \ / \
   5  6 2  3

如果要提取节点5，使用当前算法，它只会用3替换它：

       0
      / \
     4   1
    / \ /
   3  6 2

而且由于它没有孩子，完成。但这不再是最小的堆，因为3＆lt; 4，但4是3的父母。

要实现此目的，您首先需要筛选节点，然后筛选（您所谓的minheapify）：

// Swap with parent until parent is less. Returns new index
int MinHeap::siftUp(int i) 
{
    while (i > 0)
    {
        int i_parent = parent(i);
        if (harr[i_parent] < harr[i]) break;
        swap(harr[i_parent], harr[i]);
        i = i_parent;
    }
    return i;
}

// Swap with smallest child until it is smaller than both children. Returns new index
int MinHeap::siftDown(int i) {
    while (true)
    {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heap_size && harr[l] < harr[i]) smallest = l;
        if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
        if (smallest == i) break;
        swap(harr[i], harr[smallest]);
        i = smallest;
    }
    return i;
}

void MinHeap::deleteKey(int i)
{
    if (i<heap_size && i>=0)
    {
        if (i == heap_size-1)
            heap_size--;
        else
        {
            harr[i] = harr[heap_size-1];
            heap_size--;
            i = SiftUp(i);
            SiftDown(i);
        }
    }
}