java - 堆插入方法中的双项

Question

我看到将项目添加到二进制堆的奇怪行为。我添加了三个值：20,31,12. 当我检查数组中的项目时，现在有 5 个值：12,20,20,31,12. 我无法弄清楚重复项来自哪里。为什么会重复项目？

添加项目：

public void add(int x){     
    int hole = heap.size();
    heap.add(hole, x);
    bubbleUp(hole);     
}

bubbleup方法：

private void bubbleUp(int child) {
    int parent;
    Bid tmp;

    if (child != 0) {
        parent = (child-1)/2;
        if (heap.get(parent).compareTo(heap.get(child))) {
            tmp = heap.get(parent);
            heap.add(parent, heap.get(child));
            heap.add(child, tmp);                           
            bubbleUp(parent);
        }
    }
}

Answer 1

它在这里

heap.add(parent, heap.get(child));
heap.add(child, tmp); 

您要做的是交换元素。的两个参数版本add仍然添加一个元素，而不是替换该位置的先前值。

改为使用set。

Answer 2

add(int,Object)最有可能插入. 试试set(int,Object)。