0

我试图删除我的二进制堆中的最小数字，我只能删除一次最小值，但是在我尝试再次删除它之后它返回 0，它不应该返回 0，只是最小数字消失的堆。我试图调试问题并没有从中获得任何收益。如果有人能看到我看不到的东西，你能帮我看看问题吗？先感谢您。例如，在我从 1-6 插入堆后，堆中将有 5 6 1 2 3 4，在我删除 min 后，它会打印出 2 3 4 5 6。但是如果我删除 Min 之后它会打印出 0 而不是3 4 5 6. 任何解决此问题的帮助将不胜感激。

public class BHeap {

public int RemoveMin(){

            while( curr != null ) {
        if( curr.key < found.key ){
            found = curr;
            p_o = prev;
        }
        prev = curr;
        curr = curr.rightSibling;
    }

    this.root = merge(found.leftmostChild);
    return result;
}
4

1 回答 1

2

我相信在实现堆（此处为 min-heap）时，通常应该将其分为三种方法：

-Heapify（在堆的一个元素上调用：1.从{element, element.right, element.left}中选择最小的元素，2.如果需要（如果元素不是三个中最小的），交换最小的三个与元素并递归地在元素上修复堆一直向下），

-BuildHeap（只是适当地调用 Heapify），

-Extract-Min（1.将顶部元素与堆的最右边（底部最后一个）元素交换，2.删除已经交换的最小元素，3.在新的顶部元素上调用heapify（刚刚交换）修复堆。

我也相信堆是一种主要用作表结构而不是节点结构的结构。Cormen、Leiserson、Rivest、Stein 的“Introduction to Algorithms”为此提供了良好的理论基础。

至于您的实现，据我了解，您将 found 设置为当前根（这是堆中的最小元素），然后在堆中搜索较小的元素。您找不到任何键小于根的元素，否则它根本就不是最小堆！

于 2013-11-01T23:02:37.297 回答