0

http://www.cplusplus.com/reference/algorithm/make_heap/

在这个链接中。它说:

在内部,堆是一棵树,其中每个节点都链接到不大于其自身值的值。在 make_heap 生成的堆中,一个元素在树中的具体位置,而不是由消耗内存的链接确定,是由它在序列中的绝对位置确定的,其中 *first 始终是堆中的最大值。

关于“由它在序列中的绝对位置决定”。我在这里感到困惑。它还说“堆是一棵树,其中每个节点都链接到不大于其自身值的值”

这2句话矛盾吗?在这里很困惑。C++ 中的堆到底是什么树?

希望有好心人能帮帮我 非常感谢

4

2 回答 2

2

这说明堆具有典型的树状结构,其中每个“父”节点都大于或等于“子”节点的值(“......每个节点链接到的值不大于它自己的值价值...”)。

然后它继续说,它使用就地内存(也称为数组 - “......是由它在序列中的绝对位置决定...")。

*first 是堆上的第一个元素(或最大/最小,取决于比较器函数),并且始终位于数组的第 [0] 个索引处。对于每个索引 i,孩子位于 [2*i+1] 和 [2*i+2]。

希望这可以帮助。

于 2011-04-09T07:05:54.097 回答
2

如果您查看堆实现,您会看到树是作为数组实现的。i您可以在索引处的索引处找到节点下方的值2 * i+12 * i +2。所以它是一棵树,您可以通过它们在数组中的绝对位置访问元素。

于 2011-04-09T06:41:50.617 回答