在C堆元素的值更改 [英] Changing value of a heap element in C

问题描述

我已经用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.

我的code：

typedef struct edge{

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

typedef struct heap{

 edge_st* edge[100];
 int size;

 }heap;

在code重新调整看起来象下面这样：

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

}

我在做什么正在寻找与参考的结构和改变其长度值。
改变后，我再次尝试做一个heapify，但它不工作，因为我改变了元素未必是root（0）的直接孩子。如果我做

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?

推荐答案

一旦你已经修改了节点的值，需要的泡下来或泡了的

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

如果你值降低，则需要冒泡，以preserve堆属性。这意味着，你反复地与其父交换节点，直到到达根或你达到一个地步，父母比在节点你正在考虑的值。

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.

这篇关于在C堆元素的值更改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！