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

Question

我想知道什么

我想问一下以下两个问题.

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

我在互联网上查了一下,但我找不到答案.
请告诉我答案.如果你不知道C++中的所有版本,请告诉我GCC C++ 11或C++ 14的答案.

我为什么需要

我想实现Dijkstra算法的最短路径问题.

让number of vertex = |V|, number of edge = |E|图中的.
时间复杂性是O(|E| log |V|)使用二进制堆.
但时间的复杂性在于O(|E| + |V| log |V|)使用Fibonacci Heap.

如您所见,如果图形密集,时间会有很大差异.
实际上,有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;
    }
};

编辑:这不是这个问题的重复.只有时间复杂性.我还想知道使用什么类型的堆.请告诉我.

Answer 1

@IvayloStrandjev 的答案已经提到 C++ 标准不需要特定的实现，而是需要时间复杂度。所以这是依赖于实现的。既然你在问题中提到了GCC，我找到了GCC关于优先级队列实现的文档。

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

• 配对堆
• 二叉堆
• 二项式堆
• RC二项式堆
• 薄堆

并且使用的可以通过标签参数来配置。默认标记用于配对堆。所以我猜这是 GCC 中默认使用的。

编辑：正如@MartinBonner 在评论中指出的，该链接是 for__gnu_pbds::priority_queue而不是std::priority_queue。我之前错过了。

std::priority_queue使用make_heap最终使用Bits/stl_heap.h 中的 __push_heap 方法的函数。快速浏览一下代码，它看起来像是Binary Heap的实现。