半順序リストをソートするための最良の方法は何ですか？

Question

おそらく最高の小さな例を示す。
関係を考えると

A < B < C
A < P < Q 

正しい出力は次のようになります。

ABCPQ or APQBC or APBCQ ... etc.

言い換えれば、任意の順序は、与えられた関係が保有する有効です。

私は実装するのが最も簡単である溶液中で最も興味を持っていますが、速度と時間で最高のO（n）は、同様に興味深いものです。

Answer 1

これはトポロジカル整列に呼ばれます。

標準的なアルゴリズムは、それを削除して行われるまで繰り返し、出力する最小要素である。

Answer 2

いくつかの並べ替えを行います。次にように第一項に記載の第一の規則に従って第一ソート、。あなたのルールが矛盾を含んでいない限り、動作するはずです。実施するのに十分な確認は簡単ます。

Answer 3

あなたは手での配列とC ++でpop_heap、make_heapを繰り返し呼び出すことができます。