TT_*_*TT_ 5 heap priority-queue quicksort data-structures
看起来我错过了一些非常简单的事情:优先级队列的二进制堆的优点是比较快速排序的值数组？在这两种情况下,我们将值保存在数组中,insert是O(logN),delete-max在两种情况下都是O(1).在两种情况下,给定数组元素的初始构造是O(NlogN),尽管链接http://en.wikipedia.org/wiki/Heap_%28data_structure%29表明更快的Floyd算法用于二进制堆构造.但是在队列的情况下,元素可能是逐个接收的,因此这种优势消失了.此外,合并似乎对二进制堆表现更好.
那么除了合并之外,更喜欢BH的原因是什么？也许我的假设是错误的,BP仅用于研究目的.我检查了C++文档,他们提到了"堆"但当然没有必要意味着二进制堆.
有点类似的问题:什么时候使用堆作为优先级队列是个坏主意？
如果有的话请解释downvotes - 我真的想了解这一点.
二进制堆的主要优点是您可以在最初构建它之后有效地向其添加新值.假设您要使用已排序的数组备份优先级队列.如果队列中的所有值都是事先知道的,那么您可以按照您的提及对值进行排序.但是当您想要向优先级队列添加新值时会发生什么？在最坏的情况下,这可能需要时间Θ(n),因为您必须向下移动所有数组元素,以便为刚刚添加的新元素腾出空间.另一方面,插入二进制堆需要时间O(log n),这是指数级更快.
在排序数组上使用堆的另一个原因是,您只需要将一些元素出列.正如您所提到的,对数组进行排序需要时间O(n log n),但是使用聪明的算法可以在时间O(n)中构建堆.如果你需要构建一个优先级队列并从中预留k个元素,其中k事先是未知的,带有排序数组的运行时是O(n log n + k),二进制堆是O(n + k log n) ).对于小k,第二种算法要快得多.
希望这可以帮助!