The Kruskal method is O(E log E) When E is too big to make it in time - The PRIM method, in combination with the Fibonacci heap, gives an O(E+V log V) - Even with a naive binary heap we get O((E+V)log V)
This page is auto-translated from /nishio/最小全域木 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.