堆vs二叉搜索树(当它比另一个更好？)

Question

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

Answer 1

这几乎就像是比较咖啡杯和考拉熊。堆和二进制搜索树旨在执行截然不同的功能。堆是优先级队列抽象数据类型的实现。在基本级别上，优先级队列(因此是堆)只是一个放东西的袋子，当你伸手去取东西时，你总是得到袋子里最小(min-heap)或最大(max-heap)的东西。

您可以让堆具有删除任意项或更改堆中项的优先级的能力，但这些都是更高级的功能，不属于堆数据结构的传统定义的范围。

二叉搜索树是一种截然不同的东西。它是一个放东西的袋子，你可以快速伸手按键抓取任何物品，或者你可以按顺序(或相反顺序)列出所有物品。

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

但事实并非如此。您不能使用堆来替换二进制搜索树。

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

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

如果您想要实现优先级队列抽象数据类型:当您请求最小(或最大，取决于您如何定义)项时，包将快速提供给您，那么您希望使用堆。