二进制堆而不是二进制搜索树

Question

您将使用二进制堆而不是二进制搜索树的场景有哪些？

我对每个结构都有一个基本的了解。如果可能的话，我希望你能对此发表意见。

Answer 1

在优先级队列的情况下，使用二进制堆而不是二进制搜索树是很有帮助的。优先级队列需要某些功能，例如访问优先级元素、插入元素和删除最高优先级元素。堆可以分别在O(1)、O(log )和O(log )中做到这一点。但是，某些类型的二进制搜索树也可以做到这一点(请参阅:自平衡搜索树)。除此之外，优先级队列也更容易用二进制堆实现，不需要额外的指针空间，构建它们需要O(n)时间，而不是O(n log n)自平衡二进制搜索树。

二进制堆比二进制搜索树更有用的另一种情况是，如果您需要随机顺序删除并有权访问堆对象的索引。

总体而言，二进制堆很方便，因为它们使用的空间更少(通过常数因子)，并且可以使用单个数组实现，而无需担心指针。然而，归根结底，您的选择实际上取决于您尝试实现的应用程序。

Answer 2

当您需要查找数据集中的最小或最大元素时，二进制堆非常有用。二进制堆总是在根节点中具有最小或最大的元素，因此可以在固定的(O(1))时间内检索它。二进制堆可用于最大化某些算法的效率，如prim的最小生成树算法和dijkstra的最短路径算法。这两种算法都可以使用二进制堆在运行它们的图中快速找到可用的最小边。

二叉树的优点是，元素可以很容易地按顺序访问，但是管理二叉树需要比二叉堆多得多的开销。因此，如果一个二进制搜索树也可以是低效的，取决于如何和什么元素添加到它。如果树不平衡，那么使用二进制搜索树的许多效率优势就会消失。使用红黑树或abl树可以解决这个问题，但代价是维护平衡的开销。

简而言之，当人们只需要在数据集中找到最大或最小的元素时，二进制堆更好，因为它很容易访问，而且管理成本更低。二叉搜索树包含元素的特定顺序，但它们需要更多的管理。