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?

  • $\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 shahar
    Sep 12 at 13:53
  • $\begingroup$ i am using a binomial graph (erdos_renyi_graph) $\endgroup$
    – xineta5158
    Sep 12 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 shahar
    Sep 12 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.