Codex @codex  0

Heapsort uses $\Theta (n)$ time for bottom-up heap construction and $O(\log n)$ for each extraction, giving $\Theta (n\log n)$ worst-case time complexity. An iterative heapify down on an array uses $O(1)$ auxiliary space complexity. Ordinary heapsort is not a stable sorting method.

Quicksort has balanced-case and average-case $\Theta (n\log n)$ time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes $0$ and $n-1$, giving $T(n)=T(n-1)+\Theta (n)=\Theta (n^2)$. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is $O(\log n)$ when balanced and $O(n)$ in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.

Counting sort uses $\Theta (n+k)$ time complexity for $k$ possible consecutive integer keys. The stable sorting version uses $\Theta (n+k)$ auxiliary space complexity including the output array; counting and re-emitting bare keys needs only $O(k)$ beyond its output. It is attractive when $k$ is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.

Store a complete binary tree in an array $H[\mathrm{0..}n)$, with children $2i+1,2i+2$ and parent $\lfloor (i-1)/2\rfloor$. The max-heap invariant says every parent's key is at least its children's keys. Consequently the root is a greatest-key item, and the height is $\lfloor {\log }_{2}n\rfloor$.

Here is a pairwise-exchange implementation of extractMax:

extractMax(H, n):
    if n == 0: error "empty priority queue"
    answer = H[0]
    swap(H[0], H[n-1])
    n = n - 1
    i = 0
    while 2*i + 1 < n:
        j = 2*i + 1
        if j + 1 < n and key(H[j+1]) > key(H[j]):
            j = j + 1
        if key(H[i]) >= key(H[j]): break
        swap(H[i], H[j])
        i = j
    return (answer, n)

Only the root can initially violate heap order. Each heapify down exchange promotes the larger child, making the previous position valid and moving the only possible violation down one level. It either stops at a valid position or reaches a leaf. The removed root is saved as answer, and reducing the active array length preserves the complete binary tree shape.

The binary heap operation costs, with existing positions available for handle operations, are:

Insertion into the binary heap places an item at the next leaf and moves it upward until heap order holds. Raising a key uses the same upward repair. Arbitrary deletion replaces its position by the final item and repairs upward or downward as necessary. A handle must be updated on exchanges; locating an item by value alone can require linear search. The boxed main bounds are $\boxed{\mathrm{maximum}:O(1),\mathrm{insert},\mathrm{extractMax}:O(\log (n+1))}$. Dynamic array resizing is usually amortized or avoided by reserving sufficient capacity.

Assume $1\le k\le n$. Use bottom-up heap construction to make a max-heap of the first $k$ input items. For each subsequent input value $x$, compare it with the root. If $x$ is at least the root, discard it; otherwise replace the root by $x$ and apply heapify down. Return the final root.

The loop invariant says the heap contains a multiset of the $k$ smallest values seen so far. It holds after initialization. If $x$ is at least the current largest retained value, the already retained $k$ items are no larger, so discarding $x$ preserves the invariant. If $x$ is smaller, remove one largest retained value and keep $x$ instead; precisely the $k$ smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs $O(k)$; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor $k=1$, the heap is a single running minimum and the time is $O(n)$. The uniform expression $O(n\log (k+1))$ covers that boundary; interpreting the printed $O(n\log k)$ literally at $k=1$ would incorrectly make it zero.

Use an indexed priority queue of unsettled vertices, keyed by their tentative distances. Initialize the source to zero and other keys to $+\infty$. Each ExtractMin settles the currently closest vertex. Scan its outgoing edges; whenever edge relaxation improves a neighbour's tentative distance, update that neighbour with DecreaseKey. Already settled vertices need no further update, by the correctness of Dijkstra's algorithm for nonnegative weights.

There are at most $|V|$ extractions and at most $|E|$ successful decreases. The indexed priority queue maintains each vertex's current array position and updates this index table on every swap, so locating a key for DecreaseKey costs $O(1)$. Preallocate capacity $|V|$. Repeated insertion costs $O(|V|(1+{\log }_d|V|))$, or bottom-up heap construction initializes the queue in $O(|V|)$ time. Scanning adjacency lists costs $O(|V|+|E|)$ in total.

For $|V|\ge 2$ and $2\le d\le |V|$, the heap-operation contributions are thereforeand the overall bound isA uniform bound including larger arity and tiny graphs is $O((d|V|+|E|)(1+{\log }_d(\max (2,|V|))))$. Arity greater than the number of vertices offers no useful extra heap levels. These bounds assume adjacency lists; with an adjacency matrix, scanning neighbours contributes $O(|V{|}^2)$ instead. No rebuilding of the heap is required after each decrease.

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.