A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed minimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertex "v" is chosen and added to the MST, a decrease-key operation is performed on all vertices "w" outside the partial MST such that "v" is connected to "w", setting the key to the minimum of its previous value and the edge cost of ("v","w").