Удалить i-й узел из кучи

Question

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

. Существует ли какой-либо алгоритм, который уменьшает время выполнения удаления Ith узел от maxheap до O(log n), где I находится в диапазоне от 1 до N?

Answer 1

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

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