Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 8 / d / 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 $O((|V|+|E|)\log |V|)$, or $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.