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

Question

Вероятно, лучше всего проиллюстрировать небольшой пример.
Учитывая отношения

A < B < C
A < P < Q 

Правильный вывод будет

ABCPQ or APQBC or APBCQ ... etc.

Другими словами, любой порядок действителен, в котором сохраняются данные отношения.

Меня больше всего интересует решение, которое проще всего реализовать, но интересны также O (n) по скорости и времени.

Answer 1

Это называется топологическая сортировка .

Стандартный алгоритм - вывести минимальный элемент, затем удалить его и повторять до готовности.

Answer 2

Вы можете повторно вызывать make_heap, pop_heap в C ++ с имеющейся последовательностью.

Answer 3

сделать несколько сортов. Сначала сортируйте по первому правилу, затем по второму и так далее. Должно работать, если ваши правила не содержат противоречий. конечно, достаточно легко реализовать.