Latest results

I dramatically increased the time it takes to test one queue. After changing this however, I encountered a rather strange bug that caused a part of the output of a simulation run to disappear. This bug is however not critical.

The raw results I gathered:

TreeMapQueue;250000;44504685563 TreeMapQueue;250000;43510640683 TreeMapQueue;250000;43507232275 TreeMapQueue;250000;43493418310 TreeMapQueue;250000;45450831695 PairingHeapQueue;250000;126060167710 PairingHeapQueue;250000;125240863979 PairingHeapQueue;250000;145046297489 PairingHeapQueue;250000;137354103844 PairingHeapQueue;250000;144051341014 HashMapQueue;250000;52394058529 HashMapQueue;250000;51806601251 HashMapQueue;250000;51151331841 HashMapQueue;250000;53559766910 HashMapQueue;250000;52176779442 FibonacciHeapQueue;250000;54482560996 FibonacciHeapQueue;250000;54985676302 FibonacciHeapQueue;250000;54372282025 FibonacciHeapQueue;250000;53014851349 FibonacciHeapQueue;250000;52796625042 JavaPriorityQueue;250000;51551165898 JavaPriorityQueue;250000;51443365330 JavaPriorityQueue;250000;50457917413 JavaPriorityQueue;250000;52876494280 JavaPriorityQueue;250000;53129498732 SkipList;250000;58607951279 SkipList;250000;60014792829 SkipList;250000;58422165150 SkipList;250000;57934313472 SkipList;250000;60079309281 CalendarQueue;250000;42451213404 CalendarQueue;250000;44537189695 CalendarQueue;250000;42570999140 CalendarQueue;250000;40472274434 CalendarQueue;250000;42437191377 EventHeapQueue;250000;40552683898 EventHeapQueue;250000;39938462029 EventHeapQueue;250000;42589802688 EventHeapQueue;250000;42522441333 EventHeapQueue;250000;41810384506 EncapsulatedSkipList;250000;60108290120 EncapsulatedSkipList;250000;59988195877 EncapsulatedSkipList;250000;59373120898 EncapsulatedSkipList;250000;58392384034 EncapsulatedSkipList;250000;60109929789 SplayTreeQueue;250000;58798470148 SplayTreeQueue;250000;61035334794 SplayTreeQueue;250000;60905879898 SplayTreeQueue;250000;61560373083 SplayTreeQueue;250000;60811032674

which results in the following results (with the second column being percentage of the time it takes to execute that same experiment compared to the java priority queue):

EventHeapQueue	81.1046341585%
CalendarQueue	82.3477270873%
TreeMapQueue	84.4028256686%
JavaPriorityQueue	100.0%
HashMapQueue	101.213577876%
FibonacciHeapQueue	105.472458436%
SkipList	113.688895795%
EncapsulatedSkipList	116.366322336%
SplayTreeQueue	118.146464463%
PairingHeapQueue	266.442283994%

So the EventHeapQueue, CalendarQueue and TreeMapQueue are all much faster than the Java priority queue, while you should definitely stay away from the pairing heap queue and the splay tree queue.