As you can see in the subject, I post this message to know why is std::priority_queue slow.
As a background context, I am a computer engineer student and I wanted to develop some data structures for fun and improve my C++ knowledge and skills. I decided it would be fun and interesting to speed test them out with std implementations and..
I ran some tests (with stack, vector, queue, deque, priority_queue for now) where I push 480000000 elements onto the diferent data structures and pops them afterwards. I timed out the amount of time and time per call for push and pop implementations.
The results for the priority_queue tests are as follows:
Executed with a Intel Core i5-4210CPU 1.70GHz and 8Gb of RAM.
My priorityqueue implementation:
Total Push time: 0.53 seconds
Total Pop time: 0.94 seconds
STD implementation of priorityqueue
Total Push time: 11.90 seconds
Total Pop time: 147.205 seconds
Surprisingly, std::priority_queue is very slow compared to other std implementations, I ran many tests and I don't know if I'm doing things right, am I missing something? If not, why is it so slow? Is it implemented as a linked list of nodes? If so, why?
The priority queue might be a little confusing to find out in my implementation, it is called heap. It is located in file src/ads/heap.hpp, in the definition of class MinHeap, you can find out push and pop implementations for the priority_queue.
Thank you in advance for taking the time to read this
Cordially, Isauro López Cortegano