如果二进制堆涉及一半（即 1.5），如何确定它们的 parent？

Question

我正在学习二叉堆，我知道要得到左边的 child 公式是 (2 x index)+1 得到右边的 child 是 (2 x index)+2。这对我来说很有意义，但是获取 parent 节点是我不太理解的地方。我知道它的公式是 (index - 1) / 2 但如果 returns 一半 (.5) 它是如何工作的？

例如，如果我试图找到索引 3 的 parent 节点，那么那将是 (3-1)/2 ，它给你 1 所以这是有道理的，但是索引 4 呢？那将是 (4-1)/2，它给你 1.5。那么索引 4 的 parent 是索引 1 还是索引 2？看下图这样的图表显然是有道理的，因为索引 4 与索引 1 相关联，但从数学的角度来看，我只是不确定我是否理解当一半发挥作用时如何处理它.

谢谢！

Answer 1

这取决于实现它的语言。在某些语言中，当操作数是整数时，/ 表示一个整数的除法，这正是您所需要的。例如，Java 就是这种情况，其中 3/2 == 1.

如果不是，那么确实需要将结果截断为整数。 Python 例如，具有整数除法运算符 //，因此 3//2 == 1.

或者，在许多这些语言中，您可以使用移位运算符：>>1 对应于整数除以 2。

所以当 / 没有将结果截断为整数时，这里有一些等效的方法：

// Using bit shift
parentIndex = (childIndex - 1) >> 1
// Using ternary operator based on check whether number is odd
parentIndex = childIndex % 2 > 0 ? (childIndex - 1) / 2 : (childIndex - 2) / 2
// Use remainder of two to get to an even number that can be divided by 2
parentIndex = (childIndex - 2 + childIndex % 2) / 2
// Same thing, but the subtraction of 2 is taken out of the numerator
parentIndex = (childIndex + childIndex % 2) / 2 - 1
// Or doing the explicit truncation
parentIndex = floor((childIndex - 1) / 2)

如果二进制堆涉及一半（即 1.5），如何确定它们的 parent？

How do binary heaps determine their parent if it involves a half (i.e. 1.5)?

algorithm

binary-heap