Ich wurde in meiner Algorithmusklasse gebeten, einen K-Way-Merge-Algorithmus zu erstellen, der von istO(nlogk) Nach der Suche habe ich herausgefunden, dass dies durch Erstellen einer k-Länge-Prioritätswarteschlange und Einreihen in das erste Element jeder Liste erfolgen kann. Extrahieren Sie das Minimum, hängen Sie es an das Ergebnis an und ziehen Sie es aus der Liste in die Warteschlange, deren Element extrahiert wurde. Ich bin verwirrt über:

Woher weiß es, wenn eine bestimmte Liste erschöpft ist? Angenommen, eine Liste enthält kleinere Elemente als jedes andere Element in anderen Listen.

Woher weiß es, dass das Element zu welcher Liste gehört (wenn keine Struktur zum Definieren verwendet wird)?

Wie ist die zeitliche KomplexitätO(nlogk)?

BEARBEITEN:

Es wäre ein bisschen hilfreicher, wenn jemand den Algorithmus schrittweise aufschreiben könnte, denn alles, was ich gelesen habe, ist in Sätzen und es ist schwer zu verstehen, wie es ist. Wenn jemand den Algorithmus aufschreiben könnte, wäre es hilfreich, dies zu verstehen.