algorithm - 最小堆的数组表示

Question

如果数组的大小为 20 (0-19)，并且映射是从 (i-1)/2 到父级。(i-1)/2 的映射对于表示大小为 13 的最小堆意味着什么？

Answer 1

正如 Dan 所说，无论数组的大小如何，映射都是相同的。如果有帮助，这里是您提供的示例的二叉堆树，第二个 70（在第 3 级）更改为 71。

您可以通过自上而下、从左到右遍历树来获得二叉堆数组。下面是具有如下所示索引的结果数组，因此您可以轻松地将映射应用于索引并查看那里出现的值并与树再现进行交叉检查。

array  :  10 | 20 | 25 | 60 |  30 | 58 | 71 | 99 | 70 |  82 | 50 | 90 | 85
indices:   0 |  1 |  2 |  3 |   4 |  5 |  6 |  7 |  8 |   9 | 10 | 11 | 12 

我希望这能消除你的疑虑。