java 堆排序获取父级
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7956601/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Heap Sort Get Parent
提问by darksky
To get a parent of a node in a heap sort array, the calculation would be (index - 1) / 2.
要在堆排序数组中获取节点的父节点，计算将是 (index - 1) / 2。
However, assume each node takes up 4 spaces in the array. To access a record/node, I must access the first position of the four of that record. So here's an example:
但是，假设每个节点在数组中占用 4 个空间。要访问记录/节点，我必须访问该记录的四个的第一个位置。所以这是一个例子：
If a parent starts at position 4, the left child starts at position 12 and the right child starts at position 16. The equation to get the left child would be 2*position + 4and the equation to get the right child would be 2*position + 8.
如果父母从位置 4 开始，左孩子从位置 12 开始，右孩子从位置 16 开始。获得左孩子2*position + 4的等式是 ，获得右孩子的等式是2*position + 8。
What would the equation be to get the parent though? I need one equation to get the parent of either the left child or the right child, the same way index-1/2does. Would that be possible? If I need two separate equations, that wouldn't work since I don't really know if a record is a left or a right child.
但是，获得父母的等式是什么？我需要一个方程来获得左孩子或右孩子的父母，同样的方式index-1/2。那可能吗？如果我需要两个单独的方程，那将不起作用，因为我真的不知道记录是左孩子还是右孩子。
Thank you,
谢谢，
采纳答案by Aasmund Eldhuset
You should leave the first index (or, in this case, the first four indices) blank; this simplifies the calculations. So the root should be at 4-7, the root's children at 8-11 and 12-15, and so on. Given this, a node's parent is at index / 8 * 4. If you have to let the root be at 0-3, you can use (index + 4) / 8 * 4 - 4.
您应该将第一个索引（或者，在这种情况下，前四个索引）留空；这简化了计算。所以根应该在 4-7，根的孩子在 8-11 和 12-15，依此类推。鉴于此，节点的父节点位于index / 8 * 4。如果你必须让根在 0-3，你可以使用(index + 4) / 8 * 4 - 4.
(However, you should consider wrapping the four related elements in a class so that it will be easier to work with them and you can handle a single array element at a time.)
（但是，您应该考虑将四个相关元素包装在一个类中，以便更轻松地使用它们并且您可以一次处理单个数组元素。）
回答by DarthVader
Look at the following C# Min heap.
看下面的C# Min heap。
public int GetParent(int i, out int index)
{
double element = i;
index = (int)Math.Floor((element - 1) / 2);
if(index < 0)
{
return 0;
}
return _collection[index];
}
This works for regular heap impl.
这适用于常规堆实现。
you can see the rest of the MinHeap implementationhere.
您可以在此处查看MinHeap 实现的其余部分。
Usually, heap structure is backed with an array and interestingly, heap wants to start from Array1to make calculating parent and childs easy.
通常，堆结构由一个数组支持，有趣的是，堆希望从数组1开始，以便轻松计算父子对象。
if you want to modify the child, parent as you mentioned in your problem, you should consider wrapping your 4 nodes in a node but keep how heap works the way it is
如果你想修改你在问题中提到的孩子，父母，你应该考虑将你的 4 个节点包装在一个节点中，但保持堆的工作方式
