Как лучше всего отсортировать частично упорядоченный список?

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++, используя имеющуюся последовательность.