堆排序獲取父

要獲得在堆排序陣列中的節點的父，計算將是（指數 - 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

堆排序獲取父

回答

相關問題