与使用堆相比，使用带有insert（）的向量作为优先级队列的开销是多少？ （c ++）

Question

我目前正在从事一个项目，在该项目中，我实现了一个结构指针向量，用作优先级队列。我使用for循环来确定向量中的位置（如果不小于背面），然后使用insert()将结构指针放置在队列中的位置。我使用back()作为队列的开头，因此我可以维护向量的弹出功能。

我只是试图确定使用堆库是否会增加速度，因为该项目取决于时间。如果您愿意，可以提供代码，因为这是Hanoi A *搜索算法的塔，堆/向量的大小可能会大大增加。

想想我也会要求将来的知识，以便在有人断手的情况下为我节省一些调试断点改组操作。

Answer 1

我做了一个简单的基准测试，首先将N随机int插入优先级队列，然后弹出N顶部元素。

预期，当队列大小较小时，使用线性搜索排序的std::vector将获胜，而实现为最大堆的std::priority_queue将在队列大小较大时获胜。

基准代码可以找到here。