Python heapq vs. sorted complexity and performance
complexity-theory, heap, performance, python, sorting
Solution
If you use binary heap to pop all elements in order, the thing you do is basically heapsort. It is slower than sort algorightm in `sorted` function apart from it's implementation is pure python.
The `heapq` is faster than `sorted` in case if you need to add elements on the fly i.e. additions and insertions could come in unspecified order. Adding new element preserving inner order in any heap is faster than resorting array after each insertion.
The `sorted` is faster if you will need to retrieve all elements in order later.
The only problem where they can compete - if you need some portion of smallest (or largest) elements from collection. Although there are special algorigthms for that case, whether `heapq` or `sorted` will be faster here depends on the size of the initial array and portion you'll need to extract.
Problem
I'm relatively new to python (using v3.x syntax) and would appreciate notes regarding complexity and performance of heapq vs. sorted. I've already implemented a heapq based solution for a greedy 'find the best job schedule' algorithm. But then I've learned about the possibility of using 'sorted' together with operator.itemgetter() and reverse=True. Sadly, I could not find any explanation on expected complexity and/or performance of 'sorted' vs. heapq.