Hi there!

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?

You can check out the code and tests I ran here https://gitlab.com/iSauron/cpp-utils, you can also run the tests by executing:

- make all
- ./stress.test

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

Sent with [ProtonMail](https://protonmail.com/) Secure Email.