對二進制最小堆的BubbleDown操作不起作用

我想從二進制堆中提取最小值，但它不起作用。這裏是我的BubbleDown代碼：對二進制最小堆的BubbleDown操作不起作用

void heapBubbleDown(Heap * const heap, int idx) { 
    int min; 

    while(RIGHT(idx) < heap->count) { 
     min = LEFT(idx); 

     if(RIGHT(idx) < heap->count) { 
      if(heap->items[LEFT(idx)] > heap->items[RIGHT(idx)]) { 
       min = RIGHT(idx); 
      } 
     } 

     heapSwapValue(&(heap->items[idx]), &(heap->items[min])); 

     idx = min; 
    } 
}

它看起來像只交換了幾個號碼，但不是所有的人，我不明白爲什麼。我試圖用不同的方式重新編碼它，並且已經多次...

我在做什麼錯？

來源

2010-04-21 Ricardo Amaral

我不認爲問題在於它交換了幾個元素。當最小的孩子> =當前項目時，您必須停止。

我將在最後兩行改寫爲：

if (heap->items[idx] > heap->items[min]) { 
     heapSwapValue(&(heap->items[idx]), &(heap->items[min])); 
     idx = min; 
    } 
    else 
     break; 
}

來源

2010-04-21 16:23:54

謝謝......雖然我不喜歡使用休息時間，但我正在考慮在while條件中添加一個變量，但還有其他方法嗎？我想不出任何... – 2010-04-21 16:54:21

@Nazgul，不容易。在你知道之前，你必須做所有的左/右的東西。你可以保留一個布爾標誌'noptInOrderYet'，但我會使用一箇中斷。 – 2010-04-21 17:00:41

我不想休息，但感謝您的洞察力。 – 2010-04-21 17:13:11

的同時的條件是不夠的。可能是沒有合適的孩子，但你需要與左孩子交換。此外，正如Henk所建議的那樣，您需要檢查計算的最小值是否小於當前值。

來源

2010-04-21 16:32:23 tafa

tafa，是的，我錯過了。它應該是'while（LEFT（idx）< heap-> count）' – 2010-04-21 16:43:38

對二進制最小堆的BubbleDown操作不起作用

回答

相關問題