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

user_164171 0
Viewed 35003

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

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?

priority-queue complexity-theory sorting c++
10 Answers

There are a lot of great answers to this question. A reasonable "rule of thumb" is

  • If you have all your elements "up front" then choose sorting.
  • If you will be adding elements / removing minimal elements "on the fly" then use a priority queue (e.g., heap).

For the first case, the best "worst-case" sort is heap sort anyway and you'll often get better cache performance by just focusing on sorting (i.e. instead of interleaving with other operations).

user_3984610
Related