比较堆和树/

Question

我是数据结构的新手。

所以我问自己堆和树有什么不同？

我在很多文档上也看到heap是用array实现的，tree是poniters。是吗？

以及什么时候需要使用树或堆？

Answer 1

树在计算机科学中是一种表示树结构的抽象数据类型。根的一个节点可以由 child 个节点组成，其中每个 child 个节点也是树。

请注意，并非所有树都是二叉搜索树。二叉搜索树是具有 2 个定义属性的树：

• 每个节点最多有2个children

• 左边child小于parent

• 右边child大于parent

另一种特殊的树是堆。堆是特殊的，因为它具有以下 属性:

• 树中的每个节点总是小于或等于每个 child 节点。

现在如何选择实现树由您决定。通过pointers/references可以实现一棵树；节点将值和 pointers/references 存储到其 children.

树也可以实现为数组。 parent在索引0处。如果最多dchildren，则parent在索引处的第i个child k 位于索引 d*k+i。在其他条件相同的情况下，我们希望使用数组，因为与遍历指针相比，数组的速度非常快。

但是，二叉搜索树通常是使用指针实现的。这是因为两个原因。

1. 如果这是一个数组，它总是必须为最坏的情况分配足够的 space。换句话说，如果您的二叉搜索树的高度为 h，则您的数组的大小必须为 O(2^h)。这很糟糕，因为您的树只能包含 h 个元素。

2. 删的也很time-consuming。如果删除根节点，则必须向上移动整个子树以替换它。我们首先要使用二叉搜索树的原因是为了保证 O(log n) 操作，而我们不会用数组来实现。

另一方面，堆通常实现为数组，因为它的树总是完全平衡的（每个节点都有 d children 除了可能在叶子处）这意味着有很少浪费 space 所以我们不必担心 1)。此外，删除堆不会像二叉搜索树那样显着影响树的结构，因此 2) 也不适用。

Answer 2

堆是完全二叉树的一种特殊情况，其中特定节点要么大于其两个子节点，要么小于其子节点。

有两种堆：

最小堆：在此堆中，任何给定节点都小于或等于它的两个子节点。 最大堆：任何给定节点都将大于或等于它的两个子节点。

应用程序：

排序：提供最佳的排序复杂度，即。 nlogn 并就地执行它，即。不使用额外的 space。 用于计算 运行 中位数。 用于制作优先队列。