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.