java - ヒープ挿入メソッドでアイテムを 2 倍にする

Question

バイナリ ヒープに項目を追加すると、奇妙な動作が発生します。3 つの値を追加します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); 

あなたがしたいことは、要素を交換することです。の2 つの引数バージョンはadd、その位置で以前の値を置き換える代わりに、1 つの要素を追加します。

set代わりに使用してください。

Answer 2

add(int,Object)挿入している可能性が高いです。試してみてくださいset(int,Object)。