英文:
Implementing a heap: becomes inaccurate after one sift
问题
以下是翻译好的代码部分：
public void makeHeap(int[] arr)
{
for(int i = 0; i <= arr.length; i++)//对数组中的每个元素，检查其子节点并将其向下移动以构建堆
{
siftDown(arr, i);
}
}
//将新的根插入到正确的位置，通过比较顶部元素并与其较大的子节点交换
public void siftDown(int[] heap, int i)
{
int c = i * 2; //获取当前索引位置的子节点
if(c == 0) // 0*2等于0，因此将其加1以将第一个节点的父节点计入
{
c+=1;
}
if(c >= heap.length || c+1 >= heap.length) // 防止数组越界
{
return;
}
if(heap[c] < heap[c + 1]) //子节点1是否小于子节点2？
{
c += 1; //如果是，将c设为较大的子节点，以便最终向上移动
}
if(heap[i] < heap[c])//如果刚获取的父节点小于上一次循环定义的子节点，则交换两者。然后再次调用siftDown以比较子节点和父节点。
{
heap = swap(heap, i, c);//交换值
siftDown(heap, c);//再次调用以比较新根与其子节点。
}
}
//以下是swap方法
public int[] swap(int[] heap, int i, int c)
{
//将两个值存入变量中
int ele1 = heap[i];
int ele2 = heap[c];
heap[i] = ele2;//将heap[i]更改为heap[c]
heap[c] = ele1;//将heap[c]更改为heap[i]
return heap;
}
起始数字为：4,7,9,6,3,1,5。期望的输出是：9,7,5,6,3,1,4，但实际上我只能得到：9,7,4,6,3,1,5。似乎一旦4在被9替换后下移一次，算法就会出错，它会认为3和1是它的子节点，而实际上应该是1,5。
谢谢您的帮助！
英文:
I am currently trying to write a program that takes an array and makes it into a heap.
I am trying to implement a siftDown method that will take the elements of the array and make them into a heap but i am just not getting the correct output i want and im not sure why:
public void makeHeap(int[] arr)
{
for(int i = 0; i <= arr.length; i++)//for each element in the array, we we check its children and sift it down
{
siftDown(arr, i);
}
}
//insert a new root in the correct position. Byu comparing the top element and swapping it with its largest child.
public void siftDown(int[]heap, int i)
{
int c = i * 2; //grab the children of the current index we are at.
if(c == 0) // 0*2 is 0 so we make it 1 so it will register the first nodes parents
{
c+=1;
}
if(c >= heap.length || c+1 >= heap.length) // so we dont go off the end of the array
{
return;
}
if(heap[c] < heap[c + 1]) //Is child 1 less than child 2?
{
c += 1; //if it is we want c to be the greater child to eventually move upwards
}
if(heap[i] < heap[c])//If the parent we have just gotten is smaller than the child defined last loop, then we swap the two. We then call sift down again to compare child and parent.
{
heap = swap(heap,i,c);//swap the values
siftDown(heap, c);//call again to compare the new root with its children.
}
}
Here is my swap method:
public int[] swap(int[]heap, int i, int c)
{
//capture the two values in variables
int ele1 = heap[i];
int ele2 = heap[c];
heap[i] = ele2;//change heap i to heap c
heap[c] = ele1;//change heap c to heap i
return heap;
}
The starting numbers are: 4,7,9,6,3,1,5
. The output i want to get is 9,7,5,6,3,1,4 but i seem to only be able to get 9,7,4,6,3,1,5. It seems once 4 gets sifted down once after being replaced by 9, the algorithm goes out of wack and it believes that 3 and 1 are its children when 1,5 should be.
Thank you or your help!
答案1
得分: 2
int c = i * 2; // 获取当前索引的子节点。
if(c == 0) // 0*2 等于 0，所以将其加一，以便注册第一个节点的父节点
{
c+=1;
}
这段代码看起来有问题。
堆中子节点的索引应该使用适用于所有情况的通用公式。
对于基于0的数组，给定父索引parentIdx，
左子索引leftChildIdx = parentIdx * 2 + 1
右子索引rightChildIdx = parentIdx * 2 + 2
这意味着索引为0的节点的子节点是1和2，索引为1的节点的子节点是3和4，索引为2的节点的子节点是5和6，依此类推。这是正确的。
而你的代码将索引为1的节点的子节点放在了2和3处，显然是错误的。
英文:
int c = i * 2; //grab the children of the current index we are at.
if(c == 0) // 0*2 is 0 so we make it 1 so it will register the first nodes parents
{
c+=1;
}
This looks wrong to me.
The heap indices for children should be a general formula that works for all cases.
Given parentIdx in 0-based array,
leftChildIdx = parentIdx * 2 + 1
rightChildIdx = parentIdx * 2 + 2
This means children of 0 are 1 and 2, children of 1 are 3 and 4, children of 2 are 5 and 6, etc. It works.
Your code places children of 1 at 2 and 3, which is clearly wrong.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论