为什么在实现优先队列时要使用堆而不是二叉树？

Question

在我看来，堆相对于二叉树的唯一优点是可以在O(1)的复杂度内找到堆中最小的元素，而在二叉树中需要O(log(2)n)的时间。

实现优先队列时，需要从数据结构中删除最小的元素。从树和堆中删除最小的元素都需要O(log(2)n)的时间，尽管从树中删除元素可能更加复杂。但是，删除没有子节点的元素实际上非常简单。

我的问题是，在实现优先队列时为什么要使用堆而不是二叉树（在这种情况下更简单）？

- Shelef

---

如果你使用节点结构而不是数组实现了堆，那么我会相信你所说的 :)。 - Luiggi Mendoza

堆是一种相当简单的数据结构实现... - le3th4x0rbot

Answer 1

当二叉树转化为数组时，最坏情况下的时间复杂度将达到O(n)，而在堆中，时间复杂度仍为O(log(n))。您可以使用平衡二叉树，如红黑树或AVL树，但这样会使其变得更加复杂，并且需要更多的内存。

- akshay202

---

还要注意的是，BST（我假设OP所说的“二叉树”是指BST，因为他们引用了查找最小值的O(lg n)）的初始化是O(n lg n)，而二叉堆的初始化可以在O(n)内完成。 - ning

Answer 2

你的第一选择应取决于预期的访问模式以及你可能存储的数据量:...

• 如果数据量不大（比如n小于30），则未排序的数组就可以胜任;
• 如果你几乎从不添加、删除或更新元素，则排序的数组将非常适用;
• 如果n小于100万，而且你只需要搜索前面或后面的头一个元素（即排名第一或最后一个元素）， 那么堆（尤其是在随机更新元素的LRU（最近最少使用）队列中）会表现得很好， 因为平均而言这样的更新是O(1)，而不是O(log(n)));
• 如果n小于100万，而且你不确定要搜索什么，那么平衡树（如红黑树或AVL）将非常适用;
• 如果n很大（比如达到100万或更多），你最好选择B树或trie（由于平衡二叉树的性能会在n足够大时"跌落下来"：内存访问往往太分散了，缓存未命中真的开始产生影响）。

...但我建议保持选择的灵活性，这样你就可以对至少一种替代方案进行基准测试并切换到它，如果它的表现更好。

在过去的20年中，我只参与过两个应用程序，在其中堆是任何事情的最佳选择（一次是LRU，另一次是在一个令人讨厌的操作研究应用程序中恢复随机扰动k维超立方体的可加性， 在这个应用程序中，超立方体中的大多数单元格出现在k个不同的堆中，并且内存非常紧缺）。但是，在这两种情况下，它们的性能远远优于其他替代方案：比平衡树或B树快几十倍。

对于我在上面提到的超立方体问题，我的团队负责认为红黑树的性能比堆更好，但基准测试表明红黑树要慢得多（据我回忆，它们慢了大约20倍），虽然B树的速度要快得多，但堆也轻松地击败了它们。

在上述两种情况下，堆的重要特征不是查找最小值的O(1)，而是平均更新随机选择的元素的O(1)时间。

-James Barbetti（我以为我是。但验证码不停地告诉我我不是人类）

- user2307094

Answer 3

堆通常比平衡二叉树更易于实现。此外，它们需要较少的内存开销（元素可以直接存储在数组中，而无需分配树节点、指针和其他内容），潜在的性能更快（主要是由于使用单个连续数组的内存局部性）...为什么不使用它们呢？

- Louis Wasserman

Answer 4

首先，有不同的二叉树（其中一些相当困难，一些只提供平均 O(log n)），而堆是其中之一。

其次：虽然大多数树的操作都是 O(log n)，但它们更复杂，存在常数因素。

堆需要额外的常数内存，而树通常需要在每个节点中存储指针。

顺便说一下，堆非常容易，只使用数组（我不确定在Java中是否是这样实现的，但我认为是这样的）

- RiaD

---

你实际上可以仅使用数组来实现二叉树，就像堆一样，而无需使用指针。如果它是完全二叉树，甚至不会浪费空间。 - gordonk

@gordonk，但是您需要更多的数组来存储子指针（索引），不是吗？在随机删除之后，您会怎么做？任何更改都将使这些指针无效。 - RiaD

在以数组实现的二叉树中，你只需要根元素的索引，其他所有索引都可以从它派生出来。假设父节点的索引是i，则左子节点的索引始终为（2i + 1），右子节点的索引为（2i + 2）。当然，对于不完整的二叉树，这会浪费一些空间，但它确实有其优点。 - gordonk

@gordonk：好的，我明白了，你只是允许有空（未使用）的数组索引。 - RiaD

Answer 5

如果您经常使用查找或搜索操作，则最好使用平衡二叉树。线段交点代码使用平衡树而不是堆，因为这个原因。

- mszlazak