0

我已经编写了一个由节点组成的最大堆的 java 实现，该节点包含两个东西，一个字符串和一个可以从每个节点访问的双精度值。它们应该按其 double 值的等级插入。我不确定我的插入或删除是否工作不正常，但是当我尝试从堆中删除前五个最大值时，我没有得到我应该得到的东西。任何想法打嗝在哪里？其中有一些方法，例如 isfull 和 isempty 来测试它是否为空或满的基本情况...... Count 是数组中的节点总数（堆是数组）。

public boolean insert(String W, double R){

    HeapNode word = new HeapNode(W,R);
    if (isFull()){
        return false;
    }
    else {
        count++;
        heap[count - 1] = word;
        siftUp(count - 1);
    }
    System.out.println("Added");
    return true;
}

public boolean siftUp(int place){

    int parentNode;
    HeapNode tmp;
    if (place != 0) {
        //parent node of place
        //parentNode = getParentNode(place);
        parentNode = ((place-1) / 2);
        if (heap[parentNode].getDouble() < heap[place].getDouble()) {
              tmp = heap[parentNode];
              heap[parentNode] = heap[place];
              heap[place] = tmp;
              siftUp(parentNode);
        }
    }
    return true;
}

那是插入，现在是删除：

public HeapNode remove(){
    HeapNode maxValue;
    if (isEmpty()){
        return null;
    }
    else{
        // Where does the max value always reside? 
        maxValue = heap[0]; 

        // What value will take the root? Last one. 

        heap[0] = heap[count-1]; 
        count--; ;

        // Begin percolate down at index of root 
        int hole = 0; 

        int child; 
        HeapNode temp = heap[hole]; 

        while( hole * 2 + 1 < count) 
        { 
         // Index of left child of node in hole index 
         child = 2 * hole + 1; 

         //find greater child
         if(child != count && (heap[child + 1].getDouble()) > (heap[child].getDouble())) 
            child++; //swap index

         if((heap[child].getDouble()) > (temp.getDouble())) //last comparison
            heap[hole] = heap[child];
         else 
            break; 

         hole = child; 
        } 
        heap[hole] = temp; 
    }
    return maxValue;
}

我正在使用的测试用例。根据双精度值按以下顺序输入节点：1.0、0.8、0.9、0.8、1.0、0.6、1.0、1.0、0.8、1.0、0.7、1.0、0.8 删除前五个我应该得到所有 1.0？我得到 1.0, 0.8, 1.0, 0.7, 1.0 作为五个。

4

2 回答 2

1

我可以发现2个错误。

  1. 你有parentNode = (place / 2);
    方法siftup。显然您使用的是基于 0 的数组索引，因此节点 0 应该有 1 和 2 作为子节点，但是这个等式将 1 作为 2 的父节点。将
    其更改为parentNode = ((place-1) / 2);.

  2. 另一个在下一行：
    if (heap[parentNode].getDouble() > heap[place].getDouble()).
    这会将最小节点冒泡到顶部，而不是最大节点。

于 2013-11-11T03:04:41.677 回答
0

您遇到的另一个问题是您的remove方法中的以下语句：

 //find greater child
     if(child != count && (heap[child + 1].getDouble()) > (heap[child].getDouble())) 
        child++; //swap index

在这里，您已经知道了child < count，因为您在循环中对其进行了测试。但是如果(child+1) == count，那么您正在针对堆中的前一个最后一个元素测试当前元素。

我想你想要的是：

if ((child < count-1) && (heap[child + 1].getDouble()) > (heap[child].getDouble()))
于 2013-11-11T13:48:12.217 回答