What data structure will be better fit - heap or sorted array?

Question

I have a program that:

1. load some data from disk into std::map in memory. std::map keeps the data sorted.

2. save sorted data to disk

I am wondering if heap will be faster if I do this:

1. load some data from disk into std::vector in memory.

2. sort the vector

3. save the data to disk

or even using heap:

1. load some data from disk into std::vector in memory.

2. make a heap in the vector

3. pop from heap and save the data to disk

What will be fastest?

Answer 1

Asymptotically all of your approaches are O(n log n):

• Inserting an element in an std::map is logarithmic in the size of the container. Inserting n elements will be O(n log n).
• Applying std::sort on an std::vector is O(n log n).
• Creating a heap can be done in linear time with std::make_heap. However, poping an element from the heap is logarithmic in the size of the heap. Poping n elements from the heap is O(n log n).

However, I expect the approaches consisting of sorting the std::vector and the heap to be faster than the one with the std::map since they take more advantage of the cache thanks to better data locality, i.e., the elements in these two cases consist of contiguously allocated blocks in memory rather than nodes spread out in memory as with the std::map.

Note also that the approach with the std::map requires more space than the other two because of the pointers that glue the map's nodes together.