This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into two containers, then merges the containers. It uses join for pb_ds's priority queues; for the STL's priority queues, it successively pops values from one container and pushes them into the other. The test measures the average time as a function of the number of values.
(The test was executed with priority_queue_text_join_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)
The test checks the effect of different underlying data structures (see Design::Priority Queues::Implementations).
Figures NPG, NPM, and NPL show the results for the native priority queues and pb_ds 's priority queues in g++, msvc, and local, respectively.
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In this test the node-based heaps perform join in either logarithmic or constant time. The binary heap requires linear time, since the well-known heapify algorithm [clrs2001] is linear.
It would be possible to apply the heapify algorithm to the STL containers, if they would support iteration (which they don't). Barring iterators, it is still somehow possible to perform linear-time merge on a std::vector-based STL priority queue, using top() and size() (since they are enough to expose the underlying array), but this is impossible for a std::deque-based STL priority queue. Without heapify, the cost is super-linear.