更快：插入到优先级队列，或回溯排序？ [英] What's faster: inserting into a priority queue, or sorting retrospectively?

问题描述

更快：插入到优先级队列或回溯排序？

What's faster: inserting into a priority queue, or sorting retrospectively?

我生成一些项目，我需要在最后排序。我想知道，什么是更快的复杂性：它们直接插入一个priority_queue或类似的数据结构，或使用排序算法在结束？

I am generating some items that I need to be sorted at the end. I was wondering, what is faster in terms of complexity: inserting them directly in a priority_queue or a similar data structure, or using a sort algorithm at end?

推荐答案

在优先级队列中插入 项将具有渐近复杂度O（ n log n ，它不比使用 sort 一次效率更高。

Inserting n items into a priority queue will have asymptotic complexity O(n log n) so in terms of complexity, it’s not more efficient than using sort once, at the end.

无论是在实践中更高效， 。你需要测试。事实上，在实践中，即使继续插入到线性数组中（如在插入排序中，没有构建堆）可能是最有效的，即使渐进地它具有更差的运行时。

Whether it’s more efficient in practice really depends. You need to test. In fact, in practice, even continued insertion into a linear array (as in insertion sort, without building a heap) may be the most efficient, even though asymptotically it has worse runtime.

这篇关于更快：插入到优先级队列，或回溯排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！