Why is this implementation of deleting an element from heap wrong?

Question

Here is my implementation of deleting an element from Min Heap if the position of the element to be deleted is known:

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

The function MinHeapify() is as follows:

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

The structure of MinHeap is as follows:

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

This implementation of delete follows the logic that we swap the element to be deleted with the last element(I've just over-written the last element onto the element to be deleted as we don't need the element to be deleted), and then decreasing the size of the heap array. We finally Minheapify the heap from the position of the deleted element(which is now occupied by the last element). This implementation is working for some but not all test cases. What is the error with this approach?

*but not all test cases* -- Get at least one of the test cases that fails, and [debug your code](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Apr 24 '22 at 16:39

score 1 · Accepted Answer · answered Apr 24 '22 at 17:04

Consider the following min heap:

If you were to extract the node 5, with your current algorithm it would simply replace it with 3:

And since it has no children, nothing else is done. But this is not a min heap anymore, since 3 < 4, but 4 is a parent of 3.

To implement this you first need to sift-up the node, then sift-down (what you've called 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);
        }
    }
}

Why is this implementation of deleting an element from heap wrong?

1 Answers1