Лучшая структура данных для записи фронта Парето

Question

Могу ли я спросить, если кто-то уже видел или столкнулся со следующей проблемой?

Мне нужно обработать список значений стоимости / прибыли c₁/ p₁, c₂/ p₂, c₃/ p₃,..., который удовлетворяет:

• c₁≤c₂≤c₃≤c₄...
• p₁≤p₂≤p₃≤p₄...

Это пример: 2/3, 4/5, 9/15, 12/19

Если кто-то пытается вставить 10/14 в приведенном выше списке операция отклонена из-за существующей пары затраты / прибыль 9/12: никогда не полезно увеличивать стоимость (9->10) и уменьшить прибыль (14->12). Такие списки могут возникать, например, в (состояниях) алгоритмов динамического программирования для задач о ранцах, где затраты могут представлять веса.

Если один вставляет 7/20 в приведенном выше списке, это должно вызвать удаление 9/15 а также 12/19,

Я написал решение, используя C++std::set (часто реализуется с красно-черными деревьями), но мне нужно было предоставить функцию сравнения, которая в конечном итоге стала слишком сложной. Кроме того, вставка в такие наборы занимает логарифмическое время, и это может легко привести к линейному времени (с точки зрения неамортизированной сложности), например, когда вставка инициирует удаление всех других элементов.

Интересно, существуют ли лучшие решения, учитывая, что существует множество решений для реализации (упорядоченных) наборов, например, очередей с приоритетами, куч, связанных списков, хеш-таблиц и т. Д.

Это фронт Парето (obj1: минимальная стоимость, obj2: максимальная прибыль), но я все еще не смог найти лучшую структуру для его записи.

Answer 1

Я не полностью понял правила, которые вы описали, поэтому я буду агностически говорить, что попытка вставки может привести к отклонению, и если она будет принята, то последующие элементы должны быть удалены.

Вам нужно будет использовать сбалансированное дерево сравнения, представленное в виде массива. В этом случае на поиск нужных вам узлов уйдет O(logN), что будет сложностью поиска или отклоненной попытки вставки. Когда вам нужно удалить элементы, то вы удалите их и вставьте новый, который имеет сложность

O(logN + N + N + logN) (то есть поиск, удаление, перебалансировка и вставка. Мы могли бы избавиться от последнего логарифма, если во время перебалансировки мы знаем, куда будет вставлен новый элемент)

O (logN + N + N + logN) = O (2logN + 2N) = O (logN ^ 2 + 2N), что в значительной степени является линейной сложностью.