java - Java 二叉堆中的 RemoveMin

Question

我正在尝试删除二进制堆中的最小数字，并且我只能删除一次最小值，但在我尝试再次删除它后，它返回 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;
}

Answer 1

我相信在实现堆(此处为最小堆)时，您通常应该将其分为三种方法:

-Heapify(对堆中的元素调用:1. 从 {element, element.right, element.left} 中选择最小的元素，2. 如果需要(如果 element 不是三个中最小的)，则交换三个元素中最小的一个，并递归地遍历该元素以将堆一直固定下来)，

-BuildHeap(只需适当调用 Heapify)，

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

我还认为堆是一种主要用作表结构而不是节点结构的结构。 Cormen、Leiserson、Rivest、Stein 的《算法导论》为其提供了良好的理论基础。

关于您的实现，据我了解，您将找到的内容设置为当前根(这是堆中最小的元素)，然后在堆中搜索较小的元素。您找不到任何键比您的根更小的元素，否则它根本就不是最小堆!