Changing value of a heap element in C

问题:

I have implemented a min heap in C.

My heap is an array of structure. I have arranged the elements in heap according to the value of member 'length' in the structure. In my program I have to modify the 'length' of some members dynamically. After modifying this value, my heap has be reconstructed. I am finding difficulty in reconstruction part of this.

My code:

typedef struct edge{

int source;
int dest;
int length;
}edge_st;

typedef struct heap{

 edge_st* edge[100];
 int size;

 }heap;

The code to readjust looks like below:

void modifyHeap(heap* h, int ref, int newval)
{
    int i;
    for(i=0; i<h->size; i++)
    {
        if(h->edge[i]->source == ref)
        {
            if(h->edge[i]->length==INT_MAX)
            {
                h->edge[i]->length = 0;
            }
            h->edge[i]->length = h->edge[i]->length+newval;
            break;
        }
    }

    heapify(h,0,h->size);

}

What I am doing is searching for the structure with a reference and changing its length value. After changing I tried doing a heapify again , but it does not work because the element I changed may not be the immediate children of root(0). If I do

    heapify(h,i,h->size);

this also does not work since there may not be any children for i.

Is there any other way out of this problem?

回答1:

Once you've modified the value of a node, you need to bubble down or bubble up.

If you reduced the value, you need to bubble up, to preserve the heap property. That means that you iteratively exchange the node with its parent until either you reach the root or you reach a point where the parent is smaller than the value at the node you're considering.

If you increased it, you need to bubble down. That means that you iteratively look to see which of the node's children is smaller, and if it's smaller than the value at the node you're considering, you swap those two nodes. You keep going till you reach a leaf node, or reach a point where both children are larger than the value at the node you're considering.

This is a log-time operation.

Note that these operations are the same ones that you need for adding a node to the heap and for removing the min. To add a node, you put it at the bottom, and bubble up till it reaches the right place. To remove the min, you take out the root node and replace it with the last node, and then bubble down till it gets to the right place.

See the fount of all knowledge on this topic.