0

我正在尝试删除（Comparable e）对象说remove（2），但是当我尝试删除它时，它会删除堆中不正确的节点，而不是我想要删除的节点。

这就是输出的样子。

移除 Redwoods NP 之前的堆：

Bryce Canyon NP Redwoods NP Joshua Tree NP Zion NP Yosemite NP Lassen Volcanic NP 

[
null, 
Bryce Canyon NP, 
Redwoods NP, 
Joshua Tree NP, 
Zion NP, 
Yosemite NP, 
Lassen Volcanic NP
]

移除 Redwoods NP 后：

Bryce Canyon NP Redwoods NP Joshua Tree NP Zion NP Redwoods NP 

[
null, 
Bryce Canyon NP, 
Redwoods NP, 
Joshua Tree NP, 
Zion NP, 
Redwoods NP, 
Lassen Volcanic NP
]

BUILD SUCCESSFUL (total time: 1 second)

预期的

[
Bryce Canyon NP,
Joshua Tree NP, 
Zion NP, 
Yosemite NP, 
Lassen Volcanic NP
]

我的代码

public void remove(Comparable e) throws NoSuchElementException {

    if (size == 0) {
        throw new NoSuchElementException("Heap is empty! Nothing to be removed");
    }

    Comparable toRemove = e;
    System.out.println(Arrays.toString(heapData));
    Comparable temp = heapData[size-1];
    heapData[size-1] = toRemove;
    toRemove = temp;
    size--;
    maxHeapify(heapData,size);  
}

我的 Add(Comparable e) 代码方法

public void add(Comparable e) {
        if (size == heapData.length - 1) {
            doubleSize();
        }
        int position = ++size;
        for (; position > 1 && e.compareTo(heapData[position / 2]) < 0; position = position / 2) {
            heapData[position] = heapData[position / 2];
            maxHeapify(heapData, position);
        }

        heapData[position] = e;

    }
4

1 回答 1

0

这里：

toRemove = temp;

// 这行是错误的，你只是在改变堆中的对象，而不是在数组中。而是首先编写一个方法来查找 e 在数组中的位置并将临时对象分配给该位置

添加一个方法：

int findRemoveableIndex(Comparable[] input, Comparable e) {
    for(int i = 0; i < input.length; i++) {
        if(input[i].equals(e)) { // or == 
            return i;
        }
    }
    return -1;
}

然后，而不是上述分配这样做：

heapData[findRemoveableIndex(heapData, e)] = temp;
于 2019-03-27T13:00:22.393 回答