Fusió de K Llistes Ordenades

Donades $K$ llistes d’enters, cadascuna ordenada en ordre descendent, cal fusionar-les totes en una sola llista, també en ordre descendent.

L’estratègia consisteix a fer servir un max-heap que emmagatzema parells (valor, índex de llista). Inicialment, s’insereix el primer element de cada llista al heap juntament amb l’índex de la llista d’on prové. A cada pas, s’extreu el màxim del heap, s’afegeix al resultat, i s’insereix el següent element de la mateixa llista (si n’hi ha). D’aquesta manera, el heap sempre conté com a màxim $K$ elements i el procés és eficient.

Fes una funció amb la capçalera

/**
 * @brief Fusiona K llistes ordenades descendentment en una sola
 * llista ordenada descendentment.
 *
 * @param llistes Vector de K llistes, cadascuna ordenada
 * descendentment.
 * @pre Cada llista de `llistes` està ordenada en ordre descendent.
 * @post Retorna una llista amb tots els elements de totes les
 * llistes, ordenada descendentment.
 */
list<int> fusiona_llistes(
    const vector<list<int>>& llistes
);

Entrada

La primera línia conté un enter $K$ (el nombre de llistes). A continuació hi ha $K$ línies, cadascuna amb una llista no buida d’enters en ordre descendent, separats per espais.

Sortida

Una sola línia amb tots els enters fusionats en ordre descendent, separats per espais.

Observació

Als fitxers públics (icona del gatet) trobaràs: main.cc (el programa principal, amb l’entrada/sortida feta), fusio.cc (a on has d’implementar la funció), heap.hh, assert.hh i un Makefile.

Has d’implementar fusiona_llistes al fitxer fusio.cc i enviar només aquest fitxer.

Informació del problema

Autoria: Pau Fernández

Generació: 2026-03-05T11:19:01.755Z