Эффективно управлять дескриптором для массива двоичной кучи в C ++?
Есть ли способ эффективно отслеживать дескрипторы в двоичную кучу массива?
Поскольку нет быстрых поисков, встроенных в традиционные двоичные кучи, пользователям нужен ‘handle_type’ для удаления или уменьшения_ключа на произвольном элементе в куче.
Вы не можете использовать указатель или индекс в массиве, потому что операции кучи переместят местоположение элемента вокруг. Я не могу придумать простого решения, использующего только стековые структуры, как это делает традиционная реализация кучи. В противном случае мне пришлось бы использовать «new / delete», и это неэффективно.
Я не хочу слишком зацикливаться на преждевременной оптимизации, но я хочу, чтобы это было частью моей стандартной библиотеки утилит, и поэтому я хотел бы приложить немного усилий, чтобы узнать, что считается лучшим практиковаться для такого рода вещей.
Может быть, просто наивная реализация, использующая ‘new / delete’, является подходящим способом. Но я хотел бы получить совет от людей умнее меня, если это нормально.
Реализация очереди с приоритетами в стандартной библиотеке C ++, кажется, полностью обходит эту проблему, просто не поддерживая операцию «extension_key». Я пролистывал CLRS, и они упоминают эту проблему, но на самом деле не обсуждают ее:
мы не будем преследовать их здесь, кроме как отметить, что … эти ручки
нужно правильно поддерживать.
Есть ли здесь простой подход, который я пропускаю? Что делают «серьезные» библиотеки, когда им нужна куча массива общего назначения, для которой требуется операция «extension_key»?
Решение
Есть ли способ эффективно отслеживать дескрипторы в двоичном дереве массива?
Это гипотетически возможно (но не очень красиво). Внутренне, вместо хранения массива элементов, структура данных будет хранить массив указателей (или умных указателей) на структуру, содержащую пару индекса и элемента и.
-
Когда элемент впервые вставлен в позицию я в массиве структура данных будет инициализировать индекс этой структуры я.
-
Поскольку структура данных перемещает элементы вокруг массива, она должна изменить индекс, чтобы отразить новую позицию.
Результат push может быть указателем на эту структуру (возможно, обернутым в непрозрачный класс). Для того, чтобы получить доступ к конкретному элементу (например, для decrease_key), вы бы вызвали какой-нибудь метод кучи с этим возвращаемым значением. Куча будет тогда
- Знать адрес массива (это его член, в конце концов)
- Знать индекс в массиве через структуру, которую вы только что отправили.
Это могло бы таким образом реализовать decrease_key, например.
Тем не менее, есть, вероятно, лучшие (и менее громоздкие) решения. Обратите внимание, что приведенное выше решение не изменит асимптотическую сложность кучи массива, но константы будут хуже. И наоборот, если вы посмотрите на это сводная информация о времени работы кучи, вы можете видеть, что двоичная куча на самом деле не имеет хорошей производительности для decrease_key операции. Если вам это нужно, вам, вероятно, лучше использовать кучу Фибоначчи (или какую-то другую структуру данных). Это приводит к вашему последнему вопросу
Что делают «серьезные» библиотеки, когда им нужна куча массива общего назначения, для которой требуется операция «extension_key»?
Библиотеки, такие как повышение :: кучу обычно действительно реализуют другие структуры данных, более подходящие для более сложных операций (например, decrease_key). Эти структуры данных, естественно, основаны на узлах и, естественно, поддерживают возвращаемые значения, которые не так легко аннулируются, как в массиве.
Другие решения
Других решений пока нет …
detector