看来我错过了一些非常简单的东西：优先级队列的二进制堆与快速排序的值数组相比有什么优势？在这两种情况下，我们将值保存在数组中，插入的时间复杂度为 O(logN)，删除最大的时间复杂度为 O(1)。在这两种情况下，给定元素数组的初始构造都是 O(NlogN)，尽管链接http://en.wikipedia.org/wiki/Heap_%28data_struct%29 http://en.wikipedia.org/wiki/Heap_%28data_structure%29建议更快的弗洛伊德算法来构建二叉堆。但在队列的情况下，元素可能会被一个接一个地接收，因此这种优势就消失了。此外，合并对于二叉堆似乎表现更好。
那么除了合并之外，还有哪些原因选择BH呢？也许我的假设是错误的，BP仅用于研究目的。我检查了 C++ 文档，他们提到了“堆”，但当然它不一定意味着二进制堆。
有点类似的问题：什么时候使用堆作为优先级队列是一个坏主意？ https://stackoverflow.com/questions/19025317/when-is-it-a-bad-idea-to-use-a-heap-for-a-priority-queue?rq=1
二叉堆的主要优点是，您可以在最初构建它之后有效地向其中添加新值。假设您想使用已排序的数组支持优先级队列。如果预先知道队列中的所有值，您可以对这些值进行排序，正如您所提到的。但是，当您想要向优先级队列添加新值时会发生什么？在最坏的情况下，这可能需要时间 θ(n)，因为您必须向下移动所有数组元素，以便为刚刚添加的新元素腾出空间。另一方面，插入二叉堆需要时间 O(log n)，速度呈指数级增长。
在排序数组上使用堆的另一个原因是，如果您只需要使一些元素出列。正如您提到的，对数组进行排序需要时间 O(n log n)，但使用巧妙的算法，您可以在 O(n) 时间内构建堆。如果您需要构建一个优先级队列并从中保留 k 个元素，其中 k 事先未知，则排序数组的运行时间为 O(n log n + k)，二叉堆的运行时间为 O(n + k log n ）。对于较小的 k，第二种算法要快得多。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
