When editing values in a binary heap, and calling heapify again, the result is not as expected

Question

I am looking at a heap problem:

We are given a array with the index value in which we need to check if that index value in the array (i.e. the given heap tree) is in the correct position or not. If not then place the element at the correct position and this process is called heapify.

This is the example heap where values are modified:

My code:

//min-heapify
#include<bits/stdc++.h>
using namespace std;

class minHeap{
    int *arr;
    int size;
    int capacity;
    public:
        minHeap(int c){
            size = 0;
            capacity = c;
            arr = new int[c];
        }

        int left(int i) { return (2 * i + 1); }
        int right(int i) { return (2 * i + 2); }
        int parent(int i) { return (i - 1) / 2; }

        //insert fun 
        void insert(int t){
            if(size == capacity) 
                return;
                
            size++;                   
            arr[size-1] = t;   

            for(int i=size-1;i!=0 && arr[parent(i)] > arr[i];){
                swap(arr[i],arr[parent(i)]);
                i = parent(i);
            }
        }

        //print array
        void print_array(){
            for(int i=0;i<size;i++){
                cout<<arr[i]<<" ";
            }
        }

        //min-heapify
        void minHeapify(int i){

            //finding the smallest among lc rc and current node
            int lc = left(i);   //left chid
            int rc = right(i);  //left child
            int smallest = i;

            //if left child exist and smaller then current
            if(lc<size && arr[lc] < arr[i]){ 
                smallest = lc;
            }
            //if right child exist and smaller then current
            if(rc<size && arr[rc] < arr[smallest]){
                smallest = rc;
            }

            //
            if(smallest!=i){ //
                swap(arr[smallest],arr[i]);
                minHeapify(smallest);
            }
        }

        //changes the value in array
        void edit(int index,int value){
            arr[index] = value;
        }

        //show the value at any index
        int show(int index){
            return arr[index];
        }
};

int main(){

    minHeap h(15);
    h.insert(40);
    h.insert(20);
    h.insert(30);
    h.insert(35);
    h.insert(25);
    h.insert(80);
    h.insert(32);
    h.insert(100);
    h.insert(60);
    h.insert(70);

    cout<<"perfect minHeap-->"<<endl;
    h.print_array();
    cout<<endl<<endl;

    cout<<"value changed (index 0 and 3)-->"<<endl;
    h.edit(0,40);
    h.edit(3,20);
    h.print_array();
    cout<<endl<<endl;

    cout<<"passing index of 0-->"<<endl;
    h.minHeapify(0);
    cout<<"function running...\n"<<endl;
    
    cout<<"Final Array after minHeapify-->"<<endl;
    h.print_array();
    cout<<endl;

    cout<<"left of 20 is :-";
    int index = h.left(1);
    cout<<h.show(index);

    return 0;
}

As you can see in my tree diagram and represented in array form, the output should be the same as a perfect minheap: we check the left of 20 to make sure we get 25.

The heap starts at index 0.

Answer 1

This is expected behaviour. The minHeapify assumes that the children of the node at the given index are both heaps, but this is evidently not the case after having mutated the heap with those two edits. Consequently the result of calling minHeapify(0) is not guaranteed to be a heap.

To solve this, I would suggest that you alter the edit function so that it guarantees that it restores the heap immediately, and makes it unnecessary to make separate calls afterwards to restore the heap.

In order to do that I would first suggest to move the second part of the insert function into a separate siftUp function, so we can reuse that part:

    void insert(int t){
        if(size == capacity) 
            return;
            
        size++;                   
        arr[size-1] = t;   

        siftUp(size-1); // Defer this work to another function
    }

    void siftUp(int j) {
        for (int i = j; i != 0 && arr[parent(i)] > arr[i]; i = parent(i)) {
            swap(arr[i], arr[parent(i)]);
        }
    }

Then modify edit such that it either sifts the new value up or down, depending on how it is about to modify the current node's value:

    void edit(int index,int value){
        if (value < arr[index]) {
            arr[index] = value;
            siftUp(index);
        } else {
            arr[index] = value;
            minHeapify(index);
        }
    }

Now your heap will remain a valid heap even after making calls to edit. There is no more need to make an additional minHeapify call:

int main(){
    minHeap h(15);
    h.insert(40);
    h.insert(20);
    h.insert(30);
    h.insert(35);
    h.insert(25);
    h.insert(80);
    h.insert(32);
    h.insert(100);
    h.insert(60);
    h.insert(70);

    cout<<"perfect minHeap-->"<<endl;
    h.print_array();
    cout<<endl<<endl;

    cout<<"value changed (index 0 and 3)-->"<<endl;
    h.edit(0,40);
    h.edit(3,20);
    h.print_array();
    cout<<endl;

    return 0;
}

This code outputs at the end:

20 25 30 35 40 80 32 100 60 70

Which is this tree:

              20
             /  \
           25    30
         /   \   / \
        35   40 80  32
       / \   /
     100 60 70

...which is the final tree in the image you shared (except for a tiny difference at 60-70, which probably means you had those values inserted in reversed order -- but it is irrelevant for the question).

Why a single minHeapify(0) doesn't do the trick

When you edit the values in a heap without any further action, then the array no longer represents a heap. But h.minHeapify(0) can only guarantee to restore the heap when it is guaranteed that the children of node 0 are already heaps. Evidently this is not the case after the edit at index 3: the subtree rooted at index 1 is no longer a heap. And so a call to h.minHeapify(0) will not restore the heap property. minHeapify is an algorithm that only looks at a few nodes in the array, so it could never restore from just any edit in the array.

If you want the edits to not be accompanied by heap-correcting measures (by calling minHeapify or siftUp), then the only thing you can do after those edits is to rebuild the heap from scratch.

For that you can use the O(n) algorithm for turning any array into a heap:

    void buildHeap() {
        for (int i = (size - 1) / 2; i >= 0; i--)
            minHeapify(i);
    }        

In your driver code you should then replace the h.minHeapify(0) call with a call of h.buildHeap().

Note that this algorithm takes more time than a simple h.minHeapify(0) call.

A comment on your code:

int index = h.left(1);

This does not retrieve the left child of 20. This code looks at index 1 (not index 0), where the node's value is 25 (not 20).