What type of heap is used and time complexity of std::priority_queue in c++?

Question

What do I want to know

I want to ask about following two question.

• What type of heap is used in std::priority_queue in C++?
• What is the time complexity of top(), pop(), push() operation for std::priority_queue in C++?

I checked on the Internet, but I couldn't find the answer.
Please tell me the answer. If you don't know all version in C++, please tell me this answer for GCC C++11 or C++14.

Why do I need

I want to implement Dijkstra's Algorithm for shortest-path problem.

Let the number of vertex = |V|, number of edge = |E| in the graph.
The time complexity is O(|E| log |V|) with using Binary Heap.
but the time complexity is O(|E| + |V| log |V|) with using Fibonacci Heap.

As you can see, the time is very different if the graph is dense.
Actually, there's O(|V|^2) algorithm without using heaps, so I also want to know whether I have to implementate it.

My Implementation

Here's my implementation of priority queue with Binary Heap.
insert(x) is equal to push(x), and extract() is equal to top() --> pop().
But std::priority_queue is far more faster than my implementation.

#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;
    }
};

EDIT: This is not duplicate of this question. There's only about time complexity. I also want to know what type of heap is used. Please tell me simply.

Answer 1

The answer by @IvayloStrandjev already mentions that C++ standard doesn't require a specific implementation, rather it requires a time complexity. So this is implementation dependent. Since you have mentioned GCC in the question, I have found this documentation of GCC about the implementation of priority queue.

Basically it says that multiple implementations are presents:

• Paring Heap
• Binary Heap
• Binomial Heap
• RC Binomial Heap
• Thin Heap

And the one used can be be configured through a tag parameter. The default tag is for pairing heap. So I guess that's the one being used by default in GCC.

Edit: As pointed by @MartinBonner in comment, the link is for __gnu_pbds::priority_queue instead of std::priority_queue. I missed that before.

std::priority_queue uses make_heap function which eventually uses __push_heap method from bits/stl_heap.h. A quick glance at the code looks like an implementation of Binary Heap.

Answer 2

The standard does not specify the concrete implementation of the heap used but rather specifies the complexity of its operations and the memory complexity of the container. The complexities of the operations are as follows:

• top - O(1)
• pop - O(log(n))
• push - O(log(n))
• memory complexity - O(n)

Note that both the Fibonacci and th binary heap comply with these requirements. However from what I've seen usually the implementation is binary heap.

One more important remark - Fibonacci heap does have a better asympthotic complexity but its constant factor is larger, so you need a relatively big graph to make it worth using a Fibonacci heap instead of Binary Heap. This a common mistake - better asympthotic complexity does not mean the algorithm outperforms alternatives for any input.