I'm trying to generate a testcase so that Prim with complexity $$$O(N^2)$$$ is significantly faster than Prim with priority queue $$$O((N + M)log(N + M)$$$ (Here $$$N$$$ is number of vertices and $$$M$$$ is number of edges).

However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $$$N = 2500$$$ and $$$M = N * (N - 1) / 2$$$ (As polygon doesn't allow bigger constraint)).

I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).

Thanks.