Which one should be faster? I have written a script comparing both run time, initially the implementation with adjacency list and minimum heap performs faster, but as the number of nodes/edges increases, it seems the latter perform faster Is this result expected?
3
-
$\begingroup$ min heap should be faster. It just does the job with better complexity. If you are talking about actual run time, then for small graphs maybe a normal array could be faster, since its implementation is much simpler. Also, could you elaborate on the type of heap data structure you are using? (binary, binomial, Fibonacci, etc.) $\endgroup$– nir shaharCommented Sep 12, 2021 at 13:53
-
$\begingroup$ i am using a binomial graph (erdos_renyi_graph) $\endgroup$– xineta5158Commented Sep 12, 2021 at 14:41
-
$\begingroup$ I'm asking about the implementation of the heap, not the graph. Take a look here for a comparison of some of the different heap types there are $\endgroup$– nir shaharCommented Sep 12, 2021 at 17:23
Add a comment
|