hi thomas,
I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "// if (0)" in the attached file. When I uncomment that line, I get the following results (linux32):
... the pairing heap is a self adjusting data structure ... and it is recursively implemented. there are some use cases, where the heap degenerates into a linear list ... the bigger problem is the fact that the heap is implemented recursively ... that means that in some cases you can run into a recursion of O(n) ... in your example, your simply run into a stack overflow ... (there is a warning in the class reference about this issue)
What's impressive here is that pairing_heap and skew_heap have a compare count a factor 10 smaller than any other heap for the "Linear Backward" performance test.
skep heaps have an amortized complexity for all operations. pairing heaps are difficult to analyze but give pretty good real-world results ... cheers, tim