是否可以将堆作为具有父引用的树？

Question

我知道堆使用基本数组结构作为底层事物，因此您始终可以通过基于索引计算来找到对父级的引用，但是有没有一种方法可以将堆实现为没有索引并仅通过数据结构引用父节点？

类似地，搜索树是否也可以使用数组索引结构而不是左右节点引用？我在概念上不确定为什么一个人以一种方式教授而另一个以另一种方式教授/数据结构如何使它成为标准实现。我认为这是因为您始终可以在 O(1) 时间内访问堆元素，并且您只使用堆来获取一个元素。

Answer 1

有没有一种方法可以将堆实现为不带索引且仅通过数据结构引用父节点的树？

是的，您可以用那种方式实现堆。但不推荐这样做，因为根据它的定义，堆是一个几乎完整的二叉树。因此，通过使用基于数组的索引，不会浪费内存并且易于实现。

搜索树是否也可以使用数组索引结构而不是左右节点引用

是的，但是搜索树可能是倾斜的，数组实现会导致巨大的内存浪费。