在 C 中更改堆元素的值

Question

我已经在 C 中实现了一个最小堆。

我的堆是一个数组结构。我根据结构中成员“长度”的值排列了堆中的元素。在我的程序中，我必须动态修改某些成员的“长度”。修改这个值后，我的堆就被重构了。我发现重建这一部分很困难。

我的代码:

typedef struct edge{

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

typedef struct heap{

 edge_st* edge[100];
 int size;

 }heap;

重新调整的代码如下所示:

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) 的直接子元素。如果我这样做

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

这也不起作用，因为 i 可能没有任何 child 。

还有其他办法解决这个问题吗？

Answer 1

修改节点的值后，您需要冒泡或冒泡。

如果你减小了这个值，你需要向上冒泡，以保留堆属性。这意味着您迭代地交换节点及其父节点，直到您到达根或到达父节点小于您正在考虑的节点的值的点。

如果你增加了它，你需要冒泡。这意味着您反复查看节点的哪个子节点较小，如果它小于您正在考虑的节点的值，则交换这两个节点。您继续前进，直到到达叶节点，或者到达两个子节点都大于您正在考虑的节点的值的点。

这是一个日志时间操作。

请注意，这些操作与将节点添加到堆和删除最小节点所需的操作相同。要添加一个节点，请将其放在底部，然后向上冒泡直到到达正确的位置。要删除最小值，请取出根节点并将其替换为最后一个节点，然后向下冒泡直到到达正确的位置。

参见 the fount of all knowledge关于这个话题。