Heapsort (ordenación por montículo)

def heapsort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):         # 1. construir el montículo de máximos
        hundir(a, n, i)
    print("Montículo:", a)
    for fin in range(n - 1, 0, -1):             # 2. sacar el mayor una y otra vez
        a[0], a[fin] = a[fin], a[0]             # el mayor va a su sitio definitivo
        hundir(a, fin, 0)                       # y se recompone el montículo con lo que queda
        print(f"Sale el {a[fin]}: {a[:fin]} | {a[fin:]}")


def hundir(a, n, i):
    """Baja a[i] por el montículo a[0:n] hasta que sea mayor o igual que sus dos hijos."""
    while True:
        mayor, izq, der = i, 2 * i + 1, 2 * i + 2
        if izq < n and a[izq] > a[mayor]:
            mayor = izq
        if der < n and a[der] > a[mayor]:
            mayor = der
        if mayor == i:                          # ya es mayor que sus hijos
            return
        a[i], a[mayor] = a[mayor], a[i]
        i = mayor


a = [4, 10, 3, 5, 1, 8, 7]
heapsort(a)
print("Resultado:", a)

const texto = (a) => "[" + a.join(", ") + "]";

function heapsort(a) {
    const n = a.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) hundir(a, n, i);   // 1. construir el montículo de máximos
    console.log("Montículo: " + texto(a));
    for (let fin = n - 1; fin > 0; fin--) {                              // 2. sacar el mayor una y otra vez
        [a[0], a[fin]] = [a[fin], a[0]];                                 // el mayor va a su sitio definitivo
        hundir(a, fin, 0);                                               // y se recompone el montículo
        console.log(`Sale el ${a[fin]}: ${texto(a.slice(0, fin))} | ${texto(a.slice(fin))}`);
    }
}

/** Baja a[i] por el montículo a[0..n) hasta que sea mayor o igual que sus dos hijos. */
function hundir(a, n, i) {
    while (true) {
        let mayor = i;
        const izq = 2 * i + 1, der = 2 * i + 2;
        if (izq < n && a[izq] > a[mayor]) mayor = izq;
        if (der < n && a[der] > a[mayor]) mayor = der;
        if (mayor === i) return;                                          // ya es mayor que sus hijos
        [a[i], a[mayor]] = [a[mayor], a[i]];
        i = mayor;
    }
}

const a = [4, 10, 3, 5, 1, 8, 7];
heapsort(a);
console.log("Resultado: " + texto(a));

using System;

class Program {
    static string Texto(int[] a) => "[" + string.Join(", ", a) + "]";

    static void Heapsort(int[] a) {
        int n = a.Length;
        for (int i = n / 2 - 1; i >= 0; i--) Hundir(a, n, i);    // 1. construir el montículo de máximos
        Console.WriteLine("Montículo: " + Texto(a));
        for (int fin = n - 1; fin > 0; fin--) {                    // 2. sacar el mayor una y otra vez
            (a[0], a[fin]) = (a[fin], a[0]);                       // el mayor va a su sitio definitivo
            Hundir(a, fin, 0);                                     // y se recompone el montículo
            Console.WriteLine(
quot;Sale el {a[fin]}: {Texto(a[..fin])} | {Texto(a[fin..])}");
        }
    }

    // Baja a[i] por el montículo a[0..n) hasta que sea mayor o igual que sus dos hijos.
    static void Hundir(int[] a, int n, int i) {
        while (true) {
            int mayor = i, izq = 2 * i + 1, der = 2 * i + 2;
            if (izq < n && a[izq] > a[mayor]) mayor = izq;
            if (der < n && a[der] > a[mayor]) mayor = der;
            if (mayor == i) return;                                // ya es mayor que sus hijos
            (a[i], a[mayor]) = (a[mayor], a[i]);
            i = mayor;
        }
    }

    static void Main() {
        int[] a = { 4, 10, 3, 5, 1, 8, 7 };
        Heapsort(a);
        Console.WriteLine("Resultado: " + Texto(a));
    }
}

<?php
function texto(array $a): string { return "[" . implode(", ", $a) . "]"; }

function heapsort(array &$a): void {
    $n = count($a);
    for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) hundir($a, $n, $i);   // 1. construir el montículo de máximos
    echo "Montículo: " . texto($a) . "\n";
    for ($fin = $n - 1; $fin > 0; $fin--) {                            // 2. sacar el mayor una y otra vez
        [$a[0], $a[$fin]] = [$a[$fin], $a[0]];                         // el mayor va a su sitio definitivo
        hundir($a, $fin, 0);                                           // y se recompone el montículo
        echo "Sale el {$a[$fin]}: " . texto(array_slice($a, 0, $fin)) . " | " . texto(array_slice($a, $fin)) . "\n";
    }
}

/** Baja $a[$i] por el montículo $a[0..$n) hasta que sea mayor o igual que sus dos hijos. */
function hundir(array &$a, int $n, int $i): void {
    while (true) {
        $mayor = $i;
        $izq = 2 * $i + 1;
        $der = 2 * $i + 2;
        if ($izq < $n && $a[$izq] > $a[$mayor]) $mayor = $izq;
        if ($der < $n && $a[$der] > $a[$mayor]) $mayor = $der;
        if ($mayor === $i) return;                                      // ya es mayor que sus hijos
        [$a[$i], $a[$mayor]] = [$a[$mayor], $a[$i]];
        $i = $mayor;
    }
}

$a = [4, 10, 3, 5, 1, 8, 7];
heapsort($a);
echo "Resultado: " . texto($a) . "\n";

import heapq

# heapq convierte una lista normal en un montículo de mínimos
cola = [4, 10, 3, 5, 1]
heapq.heapify(cola)                                   # O(n)
while cola:
    print(heapq.heappop(cola), end=" ")               # 1 3 4 5 10: cada heappop es O(log n)

# Para un montículo de máximos se guardan los valores cambiados de signo

// JavaScript no trae cola de prioridad en su biblioteca estándar: o se programa el
// montículo a mano (como en el ejemplo) o se usa una librería.
class MonticuloMin {
    #a = [];
    meter(x) {                                         // sube el nuevo hasta su sitio: O(log n)
        const a = this.#a;
        a.push(x);
        for (let i = a.length - 1, p; i > 0 && a[p = (i - 1) >> 1] > a[i]; i = p) [a[i], a[p]] = [a[p], a[i]];
    }
    get tamaño() { return this.#a.length; }
}

// .NET 6 trae PriorityQueue<TElemento, TPrioridad>, un montículo de mínimos por prioridad
var cola = new PriorityQueue<string, int>();
cola.Enqueue("baja", 5);
cola.Enqueue("urgente", 1);
cola.Enqueue("normal", 3);
while (cola.Count > 0) Console.Write(cola.Dequeue() + " ");   // urgente normal baja

// De máximos: un IComparer al revés, Comparer<int>.Create((x, y) => y.CompareTo(x))

// La SPL trae montículos ya hechos: SplMinHeap, SplMaxHeap y SplPriorityQueue
$cola = new SplMinHeap();
foreach ([4, 10, 3, 5, 1] as $x) $cola->insert($x);
while (!$cola->isEmpty()) echo $cola->extract(), " ";     // 1 3 4 5 10: cada extract es O(log n)

$maximos = new SplMaxHeap();                              // de máximos