Lists and arrays are very general. Usually, more specific data structures can outperform general data structures. Heaps For these operations, what you really should have is a priority queue . These can be implemented in a variety of ways, including balanced binary trees, skip lists, and splay trees. My favorite is with heaps .
Heaps are easy to implement, and they are stored in an array, which is pretty efficient.
I use STL 's efficient implementation of heaps for my code. That's approximately a factor of 100 faster. However, these are worst case values. The more nodes you have, the faster the heap will be relative to an array or list. We also want to look for a low constant.