优先级队列的二进制堆的优点？ [英] Advantages of a Binary Heap for a Priority Queue?

问题描述

似乎我错过了一些非常简单的东西：比较一下优先级队列的二进制堆的优点，比如快速排序的值列表？在这两种情况下，我们将数值保留在数组中，在这两种情况下，insert为O（logN），delete-max为O（1）。在这两种情况下，给定数组元素的初始构造是O（NlogN），尽管链接 http://en.wikipedia.org/wiki/Heap_%28data_structure%29 建议更快的Floyd的二进制堆构造算法。但是在排队的情况下，元素可能被逐个接收，所以这个优点消失了。此外，合并似乎对二进制堆效果更好。

那么除了合并以外，还有什么理由选择BH？也许我的假设是错误的，BP只用于学习目的。我检查了C ++文档，他们提到一堆，但当然这并不意味着二进制堆。

有点类似的问题：什么时候使用一个优先级队列的一个坏主意？ a>

请解释downvote如果有的话 - 我真的想了解这一点。

It seems I'm missing something very simple: what are advantages of a Binary Heap for a Priority Queue comparing, say, with quick-sorted array of values? In both cases we keep values in an array, insert is O(logN), delete-max is O(1) in both cases. Initial construction out of a given array of elements is O(NlogN) in both cases, though the link http://en.wikipedia.org/wiki/Heap_%28data_structure%29 suggests faster Floyd's algorithm for the Binary Heap construction. But in case of a queue the elements are probably received one by one, so this advantage disappears. Also, merge seems to perform better for a Binary Heap.
So what are the reasons to prefer BH besides merge? Maybe my assumption is wrong, and BP is used only for studying purpose. I checked C++ docs, they mention "a heap" but of course it does not necessary means Binary heap.
Somewhat similar question: When is it a bad idea to use a heap for a Priority Queue?
Please explain downvotes if any - I really want to understand this.

推荐答案

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

The major advantage of the binary heap is that you can add new values to it efficiently after initially constructing it. Suppose you want to back a priority queue with a sorted array. If all the values in the queue are known in advance, you can just sort the values, as you've mentioned. But what happens when you the want to add a new value to the priority queue? This might take time Θ(n) in the worst case because you'd have to shift down all the array elements to make space for the new element that you just added. On the other hand, insertion into a binary heap takes time O(log n), which is exponentially faster.

另一个原因，您将使用堆排序数组是如果你只需要出现几个元素。如前所述，排序数组需要时间O（n log n），但是使用巧妙的算法，可以在时间O（n）中构建一个堆。如果需要从其中构建优先级队列和残差k个元素，其中k是预先未知的，具有排序数组的运行时是O（n log n + k），并且二进制堆是O（n + k log n ）。对于小k，第二种算法要快得多。

Another reason you'd use a heap over a sorted array is if you only need to dequeue a few elements. As you mentioned, sorting an array takes time O(n log n), but using clever algorithms you can build a heap in time O(n). If you need to build a priority queue and residue k elements from it, where k is unknown in advance, the runtime with a sorted array is O(n log n + k) and with a binary heap is O(n + k log n). For small k, the second algorithm is much faster.

希望这有帮助！

这篇关于优先级队列的二进制堆的优点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！