Реализация MinMax PriorityQueue с minValue и maxValue в O (1)
Я реализую MinMax Priority Queue на std :: multimap с возможностью иметь несколько значений для ключа, и у меня уже есть функции minKey и maxKey, написанные за O (1) сложности времени (с использованием begin () и end ()) ,
Теперь у меня проблема с реализацией minValue и maxValue. Одним из очевидных решений было бы создать структуру данных (например, с помощью std :: set) с использованием только значений этого pqueue и иметь доступ к min и max в O (1).
Очевидно, что минусами этого решения будет дублированный объем памяти, который я, конечно, не хочу.
Я думаю о решении с указателями на minValue и maxValue соответственно. Вставить в PQ будет легко, просто сравните с этими указателями … а теперь как насчет удаления?
Вставка: я могу иметь несколько значений на определенный ключ
Удаление: удаляет любое значение из определенного ключа (если ключ не существует, генерируется исключение).
Есть ли у вас какие-либо предложения о том, как реализовать minValue и maxValue в O (1) сложности времени?
заранее спасибо
Решение
Давайте вспомним, что вы хотите. Вы хотите реализовать очередь с двусторонним приоритетом для пар ключ-значение, которые должны быть отсортированы в соответствии с двумя различными функциями сравнения. Тот, который сравнивает ключевую часть пары, и тот, который сравнивает значение-часть.
На мой взгляд, это слишком много обязанностей для одного контейнера. Я бы порекомендовал вам реализовать очередь с приоритетами, которая использует только одно сравнение, и использовать две отдельные очереди с дублированным содержимым, но с другой функцией сравнения. Конечно, это дублирует структуру данных так же, как ваша параллель std::set идея, но более простая очередь приоритетов с одним сравнением, которую вы внедрили, будет более (повторно) полезной в целом. Его можно использовать даже тогда, когда пользователю нужно хранить только простые непарные типы, и ему не требуется многократная сортировка. Если размер отдельных объектов велик, вы можете хранить указатели в одном, чтобы сэкономить место, которое заняло бы дублирование.
Игнорируя совсем другое решение, такое как интервальная куча, я бы порекомендовал использовать std::mutiset пар ключ-значение вместо std::multimap потому что карта никогда не будет использоваться для поиска произвольных элементов по ключу. Вам нужно только найти первый и последний элементы в конце концов.
Если вы одержимы идеей создания нескольких правил сравнения, то для реализации очереди вы можете использовать многоиндексный контейнер. Увеличение есть библиотека таких контейнеров.
Другие решения
Других решений пока нет …