什么是排序部分有序列表的最佳方式？

Question

可能是最好用一个小例子示出。结果， 给出的关系

A < B < C
A < P < Q 

正确的输出将是

ABCPQ or APQBC or APBCQ ... etc.

在换句话说，任何顺序是有效的，其中给定的关系式成立。

我最感兴趣的是最容易实现的解决方案，但最好的O（n）的速度和时间也很有趣。

Answer 1

此被称为拓扑排序。

在标准算法是输出一个最小的元素，然后将其取出并重复，直到完成。

Answer 2

做几类。根据第一规则第一排序，然后根据第二个等等。应该工作，除非您的规则包含的矛盾。确保足够容易实现。

Answer 3

您可以反复调用make_heap，pop_heap在C ++手头的序列。