Удаление элемента из базы данных 2 кучи

Question

Предположим, мы получили 2 разных кучи - первая куча - это минимальная куча, а вторая куча - максимальная куча, вместе они содержат n различных элементов, причем не обязательно разные ключи, мне нужно удалить элемент x, который должен находиться в одна из куч, но не в обеих, так как эти кучи разные.

Удаление должно быть выполнено со сложностью O (logn).

ВНИМАНИЕ: кучи могут иметь ключи в следующем порядке:

minHeap: 6,6,6,6,6,6

maxHeap: 6,6,4,3

удалить: x-> key = 6

Как бы вы это сделали, возможно ли это сделать в требуемой сложности?

Подсказка: вы можете использовать HeapChangeKey, который может изменить ключ элемента x на любой, какой вы захотите - вы можете использовать его для всплытия элемента, который вы ищете ... (У меня было решение, если в кучах не было двойников но никто не говорит мне заранее, что ключи разные, поэтому приведенный выше пример - вот почему мне нужна ваша помощь)

Answer 1

Вы можете удалить из двоичной кучи за O (log n) время, используя следующий алгоритм:

1. Возьмите элемент, который нужно удалить, и используйте операцию всплывающего окна, чтобы поменять его с его родителем.пока он не достигнет вершины кучи.
2. Используйте стандартный шаг удаления двоичной кучи, чтобы удалить верхний элемент кучи и перебалансировать его.

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

Один из способов сделать этодополнить две кучи хеш-таблицами или бинарными деревьями поиска, отображающими значения в куче в их позиции.Таким образом, когда вам нужно удалить запись из одной или обеих куч, вы можете посмотреть в хеш-таблице, где в двоичных кучах искать элемент, и затем использовать описанную выше процедуру для удаления элементов.Возможно, вам придется обновить код для кучи элементов для обновления этих таблиц при перемещении элементов.

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

Надеюсь, это поможет!