Tri des ensembles de listes chaînées ordonnées

Question

Je recherche une solution élégante et performante au problème suivant.

Il existe 256 listes chaînées.

• Chaque liste contient les mêmes types d'objets que ceux qui contiennent entre autres un nombre entier utilisé pour définir un ordre de tri.
• Tous les numéros de toutes les listes sont uniques
• Chaque liste est triée par ordre croissant en fonction de ces numéros

Comment créer une liste triée par ordre croissant à partir de tous les objets des 256 listes chaînées d'origine? Je préférerais ne pas le forcer brutalement et avoir quelques autres idées, mais cela semble être l'un de ces problèmes pour lesquels il existe une solution standard optimale.

Answer 1

Vous pouvez utiliser une file d'attente prioritaire contenant l'élément "le plus haut" de chacune des 256 listes chaînées. Cet élément "le plus haut" est celui qui doit être inséré dans la liste résultante. De cette façon, vous pouvez simplement extraire le plus petit élément de la file prioritaire, l'insérer dans la file résultante et insérer son prochain élément dans la file prioritaire:

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())

Answer 2

si les listes individuelles sont déjà triées, l'application directe de l’ algorithme de fusion . en bref: comparez toutes les têtes et choisissez la plus petite, retirez-la de sa liste et insérez-la dans votre liste de résultats. répéter jusqu'à ce que toutes les listes de sources soient vides.

modifier: l'utilisation par Konrad d'une file d'attente prioritaire (un heap ) est un solution beaucoup plus élégante et évolutive, mais peut-être 256 listes d’entrées sont si peu nombreuses qu’une simple comparaison pourrait être plus rapide.

Answer 3

Il vous suffit de fusionner chaque liste avec la liste 128 au-dessus. (résultant en 128 listes)
Fusionnez ensuite chaque liste avec la liste 64 située au-dessus. (résultant en 64 listes)
Fusionnez ensuite chaque liste avec la liste 32 située au-dessus. (résultant en 32 listes)
Fusionnez ensuite chaque liste avec la liste 16 située au-dessus. (résultant en 16 listes)
Fusionnez ensuite chaque liste avec la liste 8 située au-dessus. (résultant en 8 listes)
Fusionnez ensuite chaque liste avec la liste 4 située au-dessus. (résultant en 4 listes)
Fusionnez ensuite chaque liste avec la liste 2 située au-dessus. (résultant en 2 listes)
Fusionnez ensuite chaque liste avec la liste 1 située au-dessus. (résultant en 1 liste)
(Vous pouvez utiliser une boucle pour ce qui précède.)

Answer 4

Vous ne dites pas combien de temps ces listes sont, mais je suppose qu'elles tiennent toutes dans la RAM en même temps. La première chose que je voudrais essayer est de les ajouter tous ensemble et d'appeler la routine de tri intégrée de mon environnement, et je verrais si cela donnait des performances acceptables. Il est facile à mettre en œuvre et à tester. Si cela ne donnait pas des performances acceptables, je choisirais la fusion avec la file d'attente prioritaire donnée par Konrad Rudolph.