[Dante1253]

Hallo,
ich hoffe auf ein wenig Hilfe bei folgender Aufgabe:

Ich habe k aufsteigend sortierte Listen L1...Lk dergleichen Länge. Ich will über alle Listen hinweg die k kleinsten Elemente auslesen. Problem daran ist, dass es asymptotisch echt schneller als k² sein soll, das heißt der mir logische Weg funktioniert nicht.

Wäre über einen Denkanstß erfreut,
danke!

edit: hat sich erledigt, manchmal kann die lösung auf der hand liegen... (kann geschlossen werden).
für die interessierten: bastel einen heap mit den k jeweils 1. elementen, wenn ein element entfernt wird ersetze es durch das nächste aus der entsprechenden liste... führe k-mal deleteMin aus => k*log(k).