Montículo y cola de prioridad

from dataclasses import dataclass


@dataclass
class Tarea:
    prioridad: int
    nombre: str


class ColaPrioridad:
    """Cola de prioridad de tareas: un montículo de mínimos por prioridad (1 = la más urgente)."""
    def __init__(self):
        self._a = []

    def meter(self, t):
        a = self._a
        a.append(t)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2].prioridad > a[i].prioridad:   # sube mientras su padre sea mayor
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def sacar(self):
        a = self._a
        minimo = a[0]
        ultimo = a.pop()                        # el último pasa a la raíz…
        if a:
            a[0] = ultimo
            i, n = 0, len(a)
            while True:                         # …y baja hasta su sitio
                menor, izq, der = i, 2 * i + 1, 2 * i + 2
                if izq < n and a[izq].prioridad < a[menor].prioridad:
                    menor = izq
                if der < n and a[der].prioridad < a[menor].prioridad:
                    menor = der
                if menor == i:
                    break
                a[i], a[menor] = a[menor], a[i]
                i = menor
        return minimo

    def vacia(self):
        return not self._a


cola = ColaPrioridad()
cola.meter(Tarea(3, "responder correos"))
cola.meter(Tarea(1, "arreglar el servidor caído"))
cola.meter(Tarea(4, "ordenar el escritorio"))
cola.meter(Tarea(2, "preparar la reunión"))
print("Ahora:", cola.sacar().nombre)
cola.meter(Tarea(0, "llamar al cliente enfadado"))
while not cola.vacia():
    t = cola.sacar()
    print(f"Después: {t.nombre} (prioridad {t.prioridad})")

/** Cola de prioridad de tareas: un montículo de mínimos por prioridad (1 = la más urgente). */
class ColaPrioridad {
    #a = [];

    meter(t) {
        const a = this.#a;
        a.push(t);
        let i = a.length - 1;
        while (i > 0 && a[(i - 1) >> 1].prioridad > a[i].prioridad) {   // sube mientras su padre sea mayor
            const p = (i - 1) >> 1;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }

    sacar() {
        const a = this.#a;
        const min = a[0];
        const ultimo = a.pop();                    // el último pasa a la raíz…
        if (a.length) {
            a[0] = ultimo;
            let i = 0;
            while (true) {                         // …y baja hasta su sitio
                let menor = i;
                const izq = 2 * i + 1, der = 2 * i + 2;
                if (izq < a.length && a[izq].prioridad < a[menor].prioridad) menor = izq;
                if (der < a.length && a[der].prioridad < a[menor].prioridad) menor = der;
                if (menor === i) break;
                [a[i], a[menor]] = [a[menor], a[i]];
                i = menor;
            }
        }
        return min;
    }

    vacia() { return this.#a.length === 0; }
}

const cola = new ColaPrioridad();
cola.meter({ prioridad: 3, nombre: "responder correos" });
cola.meter({ prioridad: 1, nombre: "arreglar el servidor caído" });
cola.meter({ prioridad: 4, nombre: "ordenar el escritorio" });
cola.meter({ prioridad: 2, nombre: "preparar la reunión" });
console.log("Ahora: " + cola.sacar().nombre);
cola.meter({ prioridad: 0, nombre: "llamar al cliente enfadado" });
while (!cola.vacia()) {
    const t = cola.sacar();
    console.log(`Después: ${t.nombre} (prioridad ${t.prioridad})`);
}

using System;

record Tarea(int Prioridad, string Nombre);

// Cola de prioridad de tareas: un montículo de mínimos por prioridad (1 = la más urgente).
class ColaPrioridad {
    private Tarea[] a = new Tarea[4];
    private int n = 0;

    public void Meter(Tarea t) {
        if (n == a.Length) Array.Resize(ref a, 2 * n);
        a[n] = t;
        int i = n++;
        while (i > 0 && a[(i - 1) / 2].Prioridad > a[i].Prioridad) {   // sube mientras su padre sea mayor
            int p = (i - 1) / 2;
            (a[i], a[p]) = (a[p], a[i]);
            i = p;
        }
    }

    public Tarea Sacar() {
        Tarea min = a[0];
        a[0] = a[--n];                                 // el último pasa a la raíz…
        int i = 0;
        while (true) {                                 // …y baja hasta su sitio
            int menor = i, izq = 2 * i + 1, der = 2 * i + 2;
            if (izq < n && a[izq].Prioridad < a[menor].Prioridad) menor = izq;
            if (der < n && a[der].Prioridad < a[menor].Prioridad) menor = der;
            if (menor == i) return min;
            (a[i], a[menor]) = (a[menor], a[i]);
            i = menor;
        }
    }

    public bool Vacia => n == 0;
}

class Program {
    static void Main() {
        var cola = new ColaPrioridad();
        cola.Meter(new Tarea(3, "responder correos"));
        cola.Meter(new Tarea(1, "arreglar el servidor caído"));
        cola.Meter(new Tarea(4, "ordenar el escritorio"));
        cola.Meter(new Tarea(2, "preparar la reunión"));
        Console.WriteLine("Ahora: " + cola.Sacar().Nombre);
        cola.Meter(new Tarea(0, "llamar al cliente enfadado"));
        while (!cola.Vacia) {
            var t = cola.Sacar();
            Console.WriteLine(
quot;Después: {t.Nombre} (prioridad {t.Prioridad})");
        }
    }
}

<?php
/** Cola de prioridad de tareas: un montículo de mínimos por prioridad (1 = la más urgente). */
class ColaPrioridad {
    private array $a = [];

    public function meter(int $prioridad, string $nombre): void {
        $a = &$this->a;
        $a[] = [$prioridad, $nombre];
        $i = count($a) - 1;
        while ($i > 0 && $a[intdiv($i - 1, 2)][0] > $a[$i][0]) {   // sube mientras su padre sea mayor
            $p = intdiv($i - 1, 2);
            [$a[$i], $a[$p]] = [$a[$p], $a[$i]];
            $i = $p;
        }
    }

    public function sacar(): array {
        $a = &$this->a;
        $min = $a[0];
        $ultimo = array_pop($a);                        // el último pasa a la raíz…
        if ($a) {
            $a[0] = $ultimo;
            $i = 0;
            $n = count($a);
            while (true) {                              // …y baja hasta su sitio
                $menor = $i;
                $izq = 2 * $i + 1;
                $der = 2 * $i + 2;
                if ($izq < $n && $a[$izq][0] < $a[$menor][0]) $menor = $izq;
                if ($der < $n && $a[$der][0] < $a[$menor][0]) $menor = $der;
                if ($menor === $i) break;
                [$a[$i], $a[$menor]] = [$a[$menor], $a[$i]];
                $i = $menor;
            }
        }
        return $min;
    }

    public function vacia(): bool { return !$this->a; }
}

$cola = new ColaPrioridad();
$cola->meter(3, "responder correos");
$cola->meter(1, "arreglar el servidor caído");
$cola->meter(4, "ordenar el escritorio");
$cola->meter(2, "preparar la reunión");
echo "Ahora: " . $cola->sacar()[1] . "\n";
$cola->meter(0, "llamar al cliente enfadado");
while (!$cola->vacia()) {
    [$prioridad, $nombre] = $cola->sacar();
    echo "Después: $nombre (prioridad $prioridad)\n";
}

import heapq


def k_mayores(datos, k):
    """Los k mayores de un flujo sin guardarlos todos: un montículo de MÍNIMOS de tamaño k.
    Su raíz es el menor de los k mayores vistos; un número nuevo solo entra si es mayor que ella."""
    mejores = []
    for x in datos:
        if len(mejores) < k:
            heapq.heappush(mejores, x)
        elif x > mejores[0]:
            heapq.heapreplace(mejores, x)   # sale el menor de los k y entra x
    return sorted(mejores, reverse=True)    # O(n log k) en tiempo y O(k) en memoria

# La biblioteca ya lo trae: heapq.nlargest(k, datos)

/** Los k mayores de un flujo sin guardarlos todos. Sin montículo en la biblioteca, se puede usar
    un array ordenado de tamaño k (O(n·k)) o el MonticuloMin del ejemplo de arriba (O(n log k)). */
function kMayores(datos, k) {
    const mejores = [];                         // de menor a mayor; mejores[0] es el listón
    for (const x of datos) {
        if (mejores.length < k || x > mejores[0]) {
            if (mejores.length === k) mejores.shift();
            let i = mejores.findIndex((y) => y > x);
            if (i < 0) i = mejores.length;
            mejores.splice(i, 0, x);
        }
    }
    return mejores.reverse();
}

// Los k mayores de un flujo sin guardarlos todos: un montículo de MÍNIMOS de tamaño k.
// Su raíz es el menor de los k mayores vistos; un número nuevo solo entra si es mayor que ella.
static List<int> KMayores(IEnumerable<int> datos, int k) {
    var mejores = new PriorityQueue<int, int>();
    foreach (int x in datos) {
        if (mejores.Count < k) mejores.Enqueue(x, x);
        else if (x > mejores.Peek()) mejores.EnqueueDequeue(x, x);   // entra x y sale el menor
    }
    var r = new List<int>();
    while (mejores.Count > 0) r.Add(mejores.Dequeue());
    r.Reverse();
    return r;                                   // O(n log k) en tiempo y O(k) en memoria
}

/** Los k mayores de un flujo sin guardarlos todos: un montículo de MÍNIMOS de tamaño $k.
    Su raíz es el menor de los k mayores vistos; un número nuevo solo entra si es mayor que ella. */
function kMayores(iterable $datos, int $k): array {
    $mejores = new SplMinHeap();
    foreach ($datos as $x) {
        if (count($mejores) < $k) $mejores->insert($x);
        elseif ($x > $mejores->top()) {
            $mejores->extract();                // sale el menor de los k
            $mejores->insert($x);
        }
    }
    return array_reverse(iterator_to_array($mejores, false));   // O(n log k), O(k) de memoria
}