Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6

Store a complete binary tree in a one-indexed array $A[\mathrm{1..}n]$, level by level. Index $i$ has parent in a rooted tree $\lfloor i/2\rfloor$ for $i>1$ and possible children in a rooted tree $2i$ and $2i+1$, present only when their indices are at most $n$. The max-heap condition is $A[\lfloor i/2\rfloor ]\ge A[i]$ for every $i>1$.

Following these inequalities from the root of a tree to any entry proves that $A[1]$ is a maximum. The heap order does not sort siblings or unrelated branches. The complete binary tree has height $\lfloor {\log }_{2}n\rfloor$, which bounds how far any single repair can travel. Store the current heap size separately from the array's capacity.

Assume the subtrees rooted at the children in a rooted tree of $i$ already obey the max-heap condition. Compare $A[i]$ with each present child and choose an index of the largest of these at most three keys. If that index is $i$, stop. Otherwise exchange the two keys, continue at the chosen child, and repeat. This is sift down, with the inequality reversed from a minimum-oriented binary heap.

The exchange repairs the old root position because its new key dominates both child roots; only the subtree receiving the displaced key can still be defective. This recursion invariant proves correctness. Each exchange descends one level and costs constant work, so the worst-case running time is $O(h)$ for subtree height $h$, hence $O(\log n)$. A small key at the root of a suitably ordered heap must descend to a leaf, so the logarithmic worst-case bound is attained.

Leaves already obey the heap order. Process indices $\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,\dots ,1$, calling the preceding repair at each. When an index is processed, its descendants have already been processed, so the repair's precondition holds. The resulting array is a max-heap.

The bound obtained by charging $O(\log n)$ to every call is unnecessarily large. The number of nodes with height at least $h$ is at most $\lfloor n/2^h\rfloor$. ThereforeThe total repair work is thus $O(n)$, and the loop itself has a linear number of iterations, giving $\Theta (n)$ for this bottom-up heap construction. Most nodes are near the leaves and require little repair.

A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:

Empty-queue inspections and removals need an explicit failure result. The index argument to increaseKey must identify the entry's current location: if callers use item handles, update their location records during swaps.

Given the target's current heap index $i$, remove it as follows. If $i=n$, discard the last entry. Otherwise replace $A[i]$ by $A[n]$ and reduce $n$ by one. If the replacement is larger than its parent in a rooted tree, use sift up; otherwise use the maximum-oriented sift down from $i$.

Only comparisons incident to the replacement can initially violate the heap order. If it exceeds its parent, it also dominates the old children because the old key dominated those children and was no larger than the parent; an upward repair suffices. Otherwise the upward comparison is valid and only a downward repair can be needed. Thus removal takes $O(\log n)$ worst-case time after the location is known. Searching an unindexed heap for an arbitrary specified key can instead require $\Theta (n)$ time; the logarithmic bound does not include such a search.

Only arrange switches towards A. For every vertex $u$, compute its degree $\mathrm{deg}(u)$ and the current number $c(u)$ of neighbours preferring A. Put the B vertices in a max-heap with key $q(u)=2c(u)-\mathrm{deg}(u)$. Maintain each vertex's current heap array index during exchanges.

While the queue is nonempty and its maximum key is positive, extract that vertex $u$, show it its neighbours' preferences, append $u$ to the answer sequence, and set its preference to A. For every neighbour $v$ still preferring B, increase $c(v)$ by one and use increaseKey to increase its heap key by two. Stop when every remaining key is nonpositive.

A positive key means precisely a strict majority of A neighbours, so every listed move is legal. Degrees never change; A neighbours never revert in this chosen sequence. An isolated B vertex has key zero and cannot be converted. Initialization costs $O(|V|+|E|)$, there are at most $|V|$ extractions, and each edge causes at most two neighbour inspections and at most a constant number of key updates. The required bound is therefore $O((|V|+|E|)\log (|V|+1))$. A simple work queue of newly eligible vertices can even implement the same monotone threshold activation in $O(|V|+|E|)$ time, since a vertex needs to be enqueued only once.

Let $C$ be the final A set produced by the algorithm. It contains the initial A set, and every vertex outside $C$ has at most half its neighbours in $C$: otherwise its final key would still be positive. Thus $C$ is closed under the activation rule.

Now consider any legal sequence, including sequences which change some A preferences back to B. We prove by induction that its current A set is always a subset of $C$. This is true initially. A switch to B preserves the inclusion. If a vertex outside $C$ were to switch to A, its A neighbours would all lie in $C$, so their number could not exceed half its degree. Such a switch is forbidden. A switch inside $C$ also preserves the inclusion.

Consequently every attainable final A set has size at most $|C|$. The algorithm supplies a legal sequence attaining $C$ itself, so its sequence is optimal. This closure dominance for asynchronous threshold switching proves more than a local-greedy claim: temporary losses of A vertices cannot unlock an additional vertex outside the activation closure.