优先级队列的二进制堆的优点？

看来我错过了一件非常简单的事情：比较一下优先级队列和二级堆的优点，比如说快速排序的数组值？在这两种情况下，我们将值保存在一个数组中，插入为O（logN），在两种情况下，delete-max均为O（1）。在这两种情况下，给定元素阵列的初始构造都是O（NlogN），但链接http://en.wikipedia.org/wiki/Heap_%28data_structure%29表示为二进制堆构造提供了更快的Floyd算法。但是在排队的情况下，这些元素可能会一个接一个地被接收，所以这个优点就消失了。另外，合并似乎对二进制堆更好。
那么除了合并之外，还有什么理由更喜欢BH？也许我的假设是错误的，BP只用于学习目的。我检查了C++文档，他们提到了“堆”，但它当然不一定意味着二进制堆。
有点类似的问题：When is it a bad idea to use a heap for a Priority Queue?
请解释downvotes，如果有的话 - 我真的想明白这一点。优先级队列的二进制堆的优点？

来源

2014-01-19 TT_

实际上，这里有很多关于SO的问题都提到了二叉树作为PQ的实现。 –

另一个比较堆和二叉树：http://stackoverflow.com/questions/15637446/why-heap-is-better-than-binary-tree-to-represent-a-priority-queue?rq=1 但是这个问题的答案在这里没有关系。 –

@templatetypedef对不起，我犯了一个错误：对于BH，delete-max是O（logN），我的意思是find-max是O（1）。我在阅读你的答案后意识到了这一点。 –

二进制堆的主要优点是可以在初始构建它之后有效地向其添加新值。假设你想用一个有序数组来返回一个优先级队列。如果队列中的所有值都事先已知，则可以按照前面所述对值排序。但是当你想要为优先队列添加一个新值时会发生什么？在最坏的情况下，这可能需要时间Θ（n），因为您必须将所有数组元素向下移动以为您刚添加的新元素留出空间。另一方面，插入到二进制堆中需要花费时间O（log n），其指数地更快。

如果你只需要出列几个元素，那么你会在一个有序数组上使用堆的另一个原因。正如你所提到的，对一个数组进行排序需要花费时间O（n log n），但是使用巧妙的算法可以在时间O（n）中构建一个堆。如果需要从中建立一个优先级队列和剩余的k个元素，其中k是未知的，则排序数组的运行时间为O（n log n + k），二进制堆为O（n + k log n ）。对于小k，第二种算法要快得多。

希望这有助于！

来源

2014-01-19 18:28:36 templatetypedef

谢谢！我会把Θ（n）的使用放在另一个+1上。我还有一个问题。当我问原来的问题时，我错过了那个转变的部分。但是可以对已排序的数组进行优化吗？在这种情况下，只有一个连续的块必须被移位，而不是BH的O（logN）交换。 –

如果你有一个n元素的数组，并且需要在它的中间插入一个元素，那么即使列表已经排序，你也需要将n/2个元素移开以腾出空间。除非您从使用阵列切换到其他数据结构，否则无法避免支付这笔费用。 – templatetypedef

优先级队列的二进制堆的优点？

回答

相关问题