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:
