哪种数据结构更适合-堆或排序数组？

Question

我有一个程序，该程序：

1. 将一些数据从磁盘加载到std::map内存中。std::map保持数据排序。

2. 将排序的数据保存到磁盘

我想知道如果这样做，堆是否会更快：

1. 将一些数据从磁盘加载到std::vector内存中。

2. 排序向量

3. 将数据保存到磁盘

甚至使用堆：

1. 将一些数据从磁盘加载到std::vector内存中。

2. 在向量中堆

3. 从堆中弹出并将数据保存到磁盘

什么是最快的？

Answer 1

渐近地，您所有的方法都是O（n log n）：

• 在元素中插入元素std::map与容器的大小是对数的。插入n个元素将是O（n log n）。
• 应用于std::sorta std::vector是O（n log n）。
• 使用可以在线性时间内创建堆std::make_heap。但是，从堆中弹出一个元素是堆大小的对数。从堆中弹出n个元素是O（n log n）。

但是，我希望排序std::vector和堆组成的方法比使用和进行排序的方法快，std::map因为由于数据位置更好，它们利用了缓存的更多优势，即，这两种情况下的元素都由内存中连续分配的块组成而不是像那样在内存中散布节点std::map。

还要注意，使用的方法std::map比其他两个方法需要更多的空间，因为指针将地图的节点粘合在一起。