对二进制最小堆的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操作不起作用

回答

相关问题