在c++中使用什么类型的堆和std::priority_queue的时间复杂度？

Question

我想知道什么

我想请教以下两个问题

• 在 C++ 中 std::priority_queue 使用什么类型的堆？
• C++中std::priority_queue的top(), pop(), push()运算的时间复杂度是多少？

我上网查了一下，没找到答案。
请告诉我答案。如果您不知道 C++ 中的所有版本，请告诉我 GCC C++11 或 C++14 的答案。

我为什么需要

我想为最短路径问题实现Dijkstra's Algorithm。

让图中的number of vertex = |V|, number of edge = |E|。
使用 Binary Heap.
的时间复杂度为 O(|E| log |V|) 但是使用 Fibonacci Heap.

的时间复杂度是 O(|E| + |V| log |V|)

如您所见，如果图形密集，时间会非常不同。
其实还有O(|V|^2)不使用堆的算法，所以我也想知道要不要实现。

我的实现

这是我使用 Binary Heap 实现的优先级队列。
insert(x) 等于 push(x)，extract() 等于 top() --> pop()。
但是 std::priority_queue 比我的实现要快得多。

#include <vector>
#include <algorithm>
using namespace std;
template<class T> class PriorityQueue {
private:
    size_t size_; vector<T> heap;
public:
    PriorityQueue() : size_(1), heap(vector<T>(1, 0)) {};
    PriorityQueue(PriorityQueue& que) : size_(que.size_), heap(que.heap) {};
    size_t size() { return size_ - 1; }
    inline void insert(int x) {
        unsigned ptr = size_++; heap.push_back(x);
        while (ptr > 1) {
            if (heap[ptr >> 1] < heap[ptr]) swap(heap[ptr], heap[ptr >> 1]);
            ptr >>= 1;
        }
    }
    inline int extract() {
        int ret = heap[1]; unsigned ptr = 1;
        while ((ptr << 1) + 1 < size_) {
            ptr <<= 1;
            if (heap[ptr] > heap[ptr + 1]) swap(heap[ptr >> 1], heap[ptr]);
            else swap(heap[ptr + 1], heap[ptr >> 1]), ptr++;
        }
        heap[ptr] = heap[--size_], heap[size_] = 0;
        while (ptr > 1) {
            if (heap[ptr >> 1] < heap[ptr]) swap(heap[ptr], heap[ptr >> 1]);
            ptr >>= 1;
        }
        heap.pop_back();
        return ret;
    }
};

编辑：这不是 this question 的副本。只有时间复杂度。我还想知道使用的是什么类型的堆。请简单的告诉我。

Answer 1

标准并没有具体规定所使用的堆的具体实现，而是规定了其操作的复杂度和容器的内存复杂度。操作复杂度如下：

• 顶部 - O(1)
• 弹出 - O(log(n))
• 推送 - O(log(n))
• 内存复杂度 - O(n)

请注意，Fibonacci 和 th 二进制堆都符合这些要求。然而，据我所见，通常实施是 binary heap.

更重要的一点 - 斐波那契堆确实具有更好的渐近复杂性，但其常数因子更大，因此您需要一个相对较大的图才能使斐波那契堆而不是二叉堆值得使用。这是一个常见的错误 - 更好的渐近复杂性并不意味着该算法优于 any 输入的替代方案。

Answer 2

@IvayloStrandjev 的回答已经提到 C++ 标准不需要特定的实现，而是需要时间复杂度。所以这取决于实现。由于你在问题中提到了 GCC，我找到了 this documentation of GCC about the implementation of priority queue.

基本上它说存在多个实现：

• 削皮堆
• 二进制堆
• 二项式堆
• RC 二项式堆
• 精简堆

并且可以通过标签参数配置使用的那个。默认标记用于 配对堆 。所以我想这就是 GCC 默认使用的那个。

编辑：正如@MartinBonner 在评论中指出的那样，link 用于__gnu_pbds::priority_queue 而不是std::priority_queue。我之前错过了。

std::priority_queue 使用 make_heap 最终使用 __push_heap method from bits/stl_heap.h 的函数。快速浏览一下代码，看起来像是 Binary Heap.

的实现