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); 

你想要做的是交换元素。 two argument version of add仍然添加一个元素，而不是替换该位置之前的值。

使用set相反。