##
Trinomial Heap Test Data

Results for the number of key comparisons, and also CPU time are available.
The test data is from using the trinomial heap for the frontier set in
Dijkstra's algorithm, then timing runs of Dijkstra's algorithm on random
graphs. Data was generated for varying graph sizes and edge densities.
The edge density of graphs can be varied in two different ways. The
first way is to vary the probability of edge existence, so the number of
edges is proportional to n^2, were n is the number of vertices in the graph.
The second way is to vary the average OUT set size (call this the edge
factor) for vertices in the graph, so that the number of edges is proportional
to n.

###
Simple Trinomial Heap

Key comparison data for varying edge factor, f:
f = 4, n = 20 to 5000 (steps of 20)
f = 8, n = 20 to 5000 (steps of 20)
f = 16, n = 20 to 5000 (steps of 20)

###
Extended Trinomial Heap

(This has O(1) worst case time for decrease_key)

Key comparison data for varying edge factor, f:
f = 4, n = 20 to 5000 (steps of 20)
f = 8, n = 20 to 5000 (steps of 20)
f = 16, n = 20 to 5000 (steps of 20)