堆排序获取父

要获得在堆排序阵列中的节点的父，计算将是（指数 - 1）/ 2。堆排序获取父

然而，假定每一个节点在阵列中占用4个空格。要访问记录/节点，我必须访问该记录中四个记录的第一个位置。所以这里有一个例子：

如果父母从第4位开始，则左边的孩子从第12位开始，右边的孩子从第16位开始。获得左边孩子的公式为2*position + 4，方程式为右边孩子将是2*position + 8。

什么是方程是获得父母？我需要一个等式来获得左侧孩子或右侧孩子的父母，与index-1/2一样。这可能吗？如果我需要两个独立的等式，那么这是行不通的，因为我不知道一个记录是左边还是右边的孩子。

谢谢

来源

2011-10-31 darksky

企业风险管理的方式，为什么会一个节点需要4空间？它需要一个。 –

因为这就是我想要的..我正在做一个堆排序的修改版本，你不必担心它的细节。 – darksky

但你要求的细节帮助;-) – phkahler

你应该离开的第一个索引（或者，在这种情况下，前四个指标）的空白;这简化了计算。所以根应该在4-7，根的孩子在8-11和12-15，依此类推。鉴于此，节点的父节点在index/8 * 4。如果您必须让根位于0-3，则可以使用(index + 4)/8 * 4 - 4。

（但是，你应该考虑包装在一个类中的四个相关的元素，这样它会更容易与他们一起工作，你可以同时处理单个数组元素。）

来源

2011-10-31 16:36:25

这不起作用。对于左边的孩子12，“12/8 * 4 = 6”和右边的孩子16，“16/8 * 4 = 8”。两者的答案应该是'4'。 – darksky

此外，我无法将这四个元素包装在一起，因为我正在处理文件中的字节。 – darksky

在整数除法中，12/8 = 1.所以12/8 * 4 = 4。不要做代数，做计算机的工作。 – phkahler

请看下面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]; 
    }

这适用于常规堆impl。

你可以在这里看到MinHeap implementation的其余部分。

通常，堆结构由数组支持，有趣的是，堆想从数组1开始，以使计算父和子容易。

，如果你要修改的子女，父母，你在你的问题中提到，你应该考虑在一个节点包裹你的4个节点，但保持堆的工作原理是

来源

2011-10-31 16:42:21 DarthVader

我无法将它们包装在一个类中，因为我正在处理字节。 – darksky

ArrayList ...... –

@BrianRoach可能适用于小事情，但考虑一个巨大的内存ARGB位图，每个像素4字节，不值得为每个像素创建一个对象/ 4长阵列。 – TWiStErRob

堆排序获取父

回答

相关问题