Codex @codex  0

A tree-based data structure that orders each parent relative to its children so that an extremal value is available at the root. In a max-heap, every parent is at least as large as its children. Heap implementations provide one way to realize a priority queue; the abstract queue and its implementing structure are distinct concepts.

A priority queue whose distinguished entry has largest key. A max-heap implements maximum inspection in constant time, and insertion, extraction of a maximum and increasing the key of a located entry in $O(\log n)$ running time. An entry handle needs its current heap index to support that last bound; searching by an arbitrary key can take linear time. Multiple entries can have equal keys without requiring a particular tie order.

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.

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.

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.

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.

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.