对于一个已排序的底层容器，为什么创建优先级队列需要 O(nlogn) 时间，而对于一个未排序的底层容器却只需要 O(n) 时间来创建？另外，为什么需要（在已排序的情况下）O(nlogn) 对优先级队列进行排序？
无论哪种情况，是否有任何有用的图表可以帮助我了解运行时间？在这些情况下使用堆会更快吗？
问问题
402 次
2 回答
0
可以使用最大堆来实现优先级队列。事实上，最大堆为我们提供了优先级队列的渐近最优实现。因此，在未排序的底层容器情况下，为了创建优先级队列，我们只需要从 n 个元素中创建一个堆，这可以使用Heapify 算法在 O(n) 时间内完成。在排序的情况下，我们需要对已知为 Theta(n) 约束的元素进行完全排序。
于 2013-02-13T11:34:03.877 回答
0
我认为您的问题一般无法回答，因为没有一种方法可以实现优先级队列。
它是由它能够执行的操作来定义的，并且有很多方法可以实现它，堆或 AVL 树只是有一些可能性。
您必须查看您用来回答此问题的 STL 实现选择的实现。
在 SGI 实现的文档中，它写道：
[2] 这个限制是priority_queue 存在的唯一原因。如果对元素的迭代很重要，您可以使用按排序顺序维护的向量、集合或使用 make_heap、push_heap 和 pop_heap 维护为堆的向量。Priority_queue 实际上是作为一个随机访问容器实现的，它被维护为一个堆。使用容器适配器priority_queue而不是手动执行堆操作的唯一原因是要清楚地表明您永远不会执行任何可能违反堆不变量的操作。
所以它似乎只是按照你的建议使用了一个堆。
于 2013-02-13T11:36:29.880 回答