Отслеживание узла внутри кучи

Question

У меня проблема: я сохраняю структуру данных, содержащую две разные кучи, минимальную кучу и максимальную кучу, что не содержит те же данные.

Моя цель - сохранить какую-либо запись для каждого местоположения узла в любой из куч и обновить ее с помощью операции кучи. Нижняя строка. Я пытаюсь выяснить, как я могу использовать функцию delete (p), которая работает в lg (n) сложности. p - объект данных указателя, который может хранить любые данные.

Спасибо, Нед.

Answer 1

Если ваша куча реализована в виде массива элементов (например, ссылок), то вы можете легко найти произвольный элемент в куче в O (n) времени. И как только вы знаете, где элемент находится в куче, вы можете удалить его в O (log n). Поэтому найти и удалить O (n + log n).

Вы можете достичь O (log n) для удаления, если вы соедините кучу со словарем или картой хэша, как я описал в this answer.

Объяснение для удаления произвольного элемента в O (log n) here.

Фокус подхода к словарю заключается в том, что словарь содержит ключ (ключ элемента) и значение, которое является позицией узла в куче. Всякий раз, когда вы перемещаете узел в кучу, вы обновляете это значение в словаре. В этом случае вставка и удаление в этом случае немного медленнее, потому что они требуют внесения в журнал (n) обновлений словарей. Но эти обновления - O (1), так что это не hugely дорогой.

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

Настоящий фактический результат добавления и удаления min (или удаления max для максимальной кучи) в парной структуре данных будет ниже, чем при стандартной куче, реализованной в виде массива, если вы не используете делая много произвольных удалений. Если вы произвольно удаляете произвольный элемент за раз, особенно если ваша куча довольно мала, вам, вероятно, лучше работать с производительностью O (n). Его проще реализовать, и когда n мало, существует небольшая реальная разница между O (n) и O (log n).