堆与二叉搜索树（当它比另一个更好时？）

Question

在什么情况下使用最小堆比使用二叉搜索树更有效？在二叉搜索树中找到最小值的时间是否等于在最小堆中找到最小值 - O(1)？

Answer 1

这几乎就像比较咖啡杯和考拉熊。堆和二叉搜索树旨在执行非常不同的功能。堆是优先队列抽象数据类型的实现。在基本层面上，优先级队列（因此​​是堆）只是一个你放东西的袋子，当你伸手拿东西时，你总是得到最小的（最小堆）或最大的（最大堆）包里的物品。

您可以幻想并赋予您的堆删除任意项目的能力，或更改堆中项目的优先级，但这些是更高级的功能，不属于堆数据的传统定义的范围结构体。

二叉搜索树是一个非常不同的野兽。这是一个可以放东西的袋子，您可以快速伸手拿取任何物品，也可以按顺序（或相反顺序）列出所有物品。

您可以使用二叉搜索树来实现优先级队列，这意味着您原则上可以用二叉树替换堆。二叉搜索树的性能不如堆，但它可以完成工作。

但反过来就不是这样了。您不能使用堆来替换二叉搜索树。

因此，哪个更好的问题实际上是您想做什么的问题？

如果您想要一组有序的项目，您可以从中快速定位任何项目，或者您可以按顺序遍历，那么您需要二叉搜索树。

如果你想要一个优先队列抽象数据类型的实现：一个包，当你要求它时，它会迅速给你最小（或最大，取决于你如何定义它）的项目，那么你想要使用堆。