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

Question

What i want to know

I want to ask about the following two questions.

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

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

Why do i need

I want to implement Dijkstra Algorithm for the shortest path.

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

As you can see, time is very different if the graph is tight.
Actually, there is an O(|V|^2) algorithm without using a heap, so I also want to know if I should implement it.

My implementation

Here is my implementation of the priority queue with Binary Heap .
insert(x) is equal to push(x) , and extract() is equal to top() --> pop() .
But std :: priority_queue is much 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 a duplicate of this question . There is only about time complexity. I also want to know what type of heap is used. Please tell me simply.

Answer 1

The answer from @IvayloStrandjev already mentions that the C ++ standard does not require a specific implementation, but requires temporary complexity. So it depends on the implementation. Since you mentioned GCC in the question, I found this GCC documentation on priority queue implementation .

Basically, this suggests that several implementations are presented:

• Paring heap
• Binary heap
• Binomial pile
• RC Binomial Heap
• Thin pile

And the one that is used can be configured using the tag parameter. The default tag for pairing . Therefore, I assume the one used by default in GCC.

Change As pointed out by @MartinBonner's comment, the link is for __gnu_pbds::priority_queue instead of std::priority_queue . I have missed this before.

std::priority_queue uses the make_heap function, which ultimately uses the __ push_heap method from / stl _heap.h bits . A quick look at the code looks like an implementation of Binary Heap .

Answer 2

The standard does not specify the specific implementation of the heap used, but rather determines the complexity of its operations and the complexity of the container’s memory. The difficulties of operations are as follows:

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

Note that both binary heaps Fibonacci and th meet these requirements. However, from what I saw, the implementation is usually a binary heap .

Another important point is that the Fibonacci heap has better asymptotic complexity, but its constant coefficient is greater, so you need a relatively large graph so that it can use the Fibonacci heap instead of the binary heap. This common mistake - the best asymptotic complexity does not mean that the algorithm outperforms the alternatives for any input.