Was ist der beste Weg, um eine teilweise geordnete Liste zu sortieren?

Question

Wahrscheinlich mit einem kleinen Beispiel am besten dargestellt.
In Anbetracht der Beziehungen

A < B < C
A < P < Q 

Die korrekten Ausgänge wären

ABCPQ or APQBC or APBCQ ... etc.

Mit anderen Worten, jede Bestellung ist gültig, in dem die angegebenen Beziehungen halten.

Ich bin sehr interessiert an der Lösung, die am einfachsten zu implementieren ist, aber die beste O (n) in der Geschwindigkeit und Zeit ist auch interessant.

Answer 1

Das heißt topologische Sortierung .

Der Standard-Algorithmus zur Ausgabe ist ein minimales Element, dann entfernen und wiederholen, bis getan.

Answer 2

verschiedene Arten tun. Sortierung nach der ersten Regel, dann entsprechend die zweiten und so weiter. Sollte funktionieren, es sei denn, Ihre Regeln Widersprüche enthalten. sicher, einfach genug zu implementieren.

Answer 3

Sie können wiederholt aufrufen make_heap, pop_heap in C ++ mit der Sequenz auf der Hand.