I want to ask about following two question.
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.
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.
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.
The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property. Thus, the insertion operation has a worst-case time complexity of O(log n). For a random heap, and for repeated insertions, the insertion operation has an average-case complexity of O(1).
Building a binary heap will take O(n) time with Heapify() . When we add the elements in a heap one by one and keep satisfying the heap property (max heap or min heap) at every step, then the total time complexity will be O(nlogn) . Because the general structure of a binary heap is of a complete binary tree.
Yes, in C++ priority_queue, we may have duplicate values.
In the worst case (element inserted at the bottom has to be swapped at every level from bottom to top up to the root node to maintain the heap property), 1 swap is needed on every level. Therefore, the maximum no of times this swap is performed is log n. Hence, insertion in a heap takes O(log n) time.
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:
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.
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:
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With