This test inserts a number of values with i.i.d integer keys into a container using push . It measures the average time for push as a function of the number of values.
(The test was executed with priority_queue_random_intpush_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; Figures NBPG, NBPM, and NBPL shows the results for the binary-heap based 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 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:
Binary heaps are the most suited for sequences of push and pop operations of primitive types (e.g. ints). They are less constrained than any other type, and since it is very efficient to store such types in arrays, they outperform even pairing heaps. (See Priority Queue Text push Timing Test for the case of non-primitive types.)
Priority-Queue Performance Tests::Observations discusses this further and summarizes.