我正在处理堆实践中的实践数据结构问题
目的是为具有给定数组的最小堆创建一个构造函数。作者已经为我们提供了高级算法，“完成后，如果您只是“冒泡”所有非叶节点，则从最后一个非叶节点开始，直到根节点为止数组将重新排列为正确的堆顺序”
这是我编码该算法的方式
public HeapPriorityQueue(E[] theElements) {
elements = theElements;
size = 0;
int len = theElements.length;
for(int c= len - 1;c>=1; c --) {
if(elements[c] != null) {
size ++;
if(hasLeftChild(c))
bubbleDown(c);
}
}
}
有人看到代码有问题吗？我确保从“非叶节点到根节点”开始，方法是从数组的末尾开始，一直到代表堆根的索引1。在调用提供的冒泡方法之前，我什至还要确保检查该节点是否为非叶节点。
当输入[null, b, f, a, z, x, k, q, j]
My代码时，会产生的输出[a, f, b, z, x, k, q, j]，该输出与的预期输出不匹配[a, f, b, j, x, k, q, z]。我知道为什么不这样（z没冒泡）。
有谁知道如何修复此程序，以便它可以匹配预期的输出？奇怪的是，在我的代码中，“ z”不会冒泡，但是“ b”会冒泡。
这是作者要实现的最小堆，您需要将此构造函数添加到Stepp Min Heap中
问题是我过早地重置了尺寸。
这是作者的hasLeftChild（）的实现
private boolean hasLeftChild(int index) {
return leftChild(index) <= size;
}
private int leftChild(int index) {
return index * 2;
}
通过将大小设置为零，并从头到尾每次进行递增，当达到“ z”或索引4时，大小字段将仅为5，而不是其预期值8。在图8中，对hasLeftChild的调用将评估为true，并且'z'将冒泡。但是，无论如何，泡沫永远不会被呼唤。
这就是我固定代码并通过所有测试的方式。
public HeapPriorityQueue(E[] theElements) {
elements = theElements;
size = theElements.length - 1;
int len = theElements.length;
for(int c= len - 1;c>=1; c --) {
if(elements[c] != null) {
if(hasLeftChild(c)){
bubbleDown(c);
}
}
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句