堆插入方法中的雙項目

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

add(int,Object)很可能是插入。試試set(int,Object)。

Answer 2

它在這裏

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

你想要做什麼是交換的元素。 two argument version of add仍然添加一個元素，而不是替換位置上的以前的值。使用set代替。