= Solution
An indexed <binary heap> builds the initial queue in $O(|V|)$ time; `extract_min` and `decrease_key` each cost $O(\log |V|)$, while a position table supports membership in $O(1)$. There are $|V|$ extractions and at most $2|E|$ edge inspections, with at most one successful decrease per inspection. Thus the bound is \b[$O((|V|+|E|)\log |V|)$], or \b[$O(|E|\log |V|)$] for a connected graph with at least two vertices. The singleton case is constant time. An unindexed heap cannot provide decrease-key by vertex without an additional position structure.
Back to article page
