更改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。