堆插入方法中的双项目

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代替。