更改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，但它不起作用，因为我更改的元素可能不是根（0）的直接子元素。如果我这样做

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

这也不起作用，因为可能没有任何孩子对我。

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

Answer 1

一旦您修改了节点的值，您需要冒泡或冒泡。

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

如果你增加了它，你需要泡下去。这意味着你迭代地查看哪个节点的子节点较小，如果它小于你正在考虑的节点的值，则交换这两个节点。你继续前进直到你到达一个叶节点，或者到达一个点，其中两个孩子都大于你正在考虑的节点的值。

这是一个日志时间操作。

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

有关该主题的信息请参见the fount of all knowledge。