Я понимаю, как удалить корень node из максимальной кучи, но является ли процедура удаления node из середины, чтобы удалить и заменить корень до тех пор, пока не будет удален желаемый node?
Является ли O (log n) оптимальной сложностью для этой процедуры?
Это влияет на большую сложность O, поскольку другие узлы должны быть удалены, чтобы удалить конкретный node?
На самом деле вы можете без проблем удалить элемент из середины кучи.
Идея состоит в том, чтобы взять последний элемент в куче и, начиная с текущей позиции (т.е. позиции, в которой был сохранен элемент, который вы удалили), просеивайте его, если новый элемент больше, чем родительский элемент старого элемента. Если он не больше родительского, то просеите его.
Это процедура для максимальной кучи. Разумеется, для небольшой кучи вы можете отменить все больше и меньше случаев.
Поиск элемента в куче - это операция O (n), но если вы уже знаете, где она находится в куче, удаление ее - O (log n).
Несколько лет назад я опубликовал очередь приоритетов для кучи для DevSource. См. Приоритетная реализация очереди на С#. Он имеет метод RemoveAt, который делает то, что я описал.
Полный источник находится в http://www.mischel.com/pubs/priqueue.zip
Проблема с удалением произвольного элемента из кучи заключается в том, что вы не можете ее найти.
В куче поиск произвольного элемента O(n), поэтому удаление элемента [если задано значением] равно O(n).
Если вам важно удалить произвольные элементы из структуры данных, куча, вероятно, не самый лучший выбор, вы должны рассмотреть все отсортированные структурированные структуры данных, например сбалансированный BST или список пропуска.
Если ваш элемент указан по ссылке, однако его можно удалить в O(logn), просто "заменив" его последним листом [помните, что куча реализована как полное двоичное дерево, поэтому есть последний лист, и вы точно знаете, где это), удалите этот элемент и повторно перечислите соответствующую кучу.
Если у вас есть максимальная куча, вы можете реализовать это, присвоив значение, большее, чем любое другое (например, что-то вроде int.MaxValue или inf в том, какой язык вы используете), возможно для элемента, который нужно удалить, -удалить, и это будет новый корень. Затем выполните регулярное удаление корня node.
Это приведет к повторному переизлучению, но я не вижу очевидного способа избежать этого дважды. Это говорит о том, что, возможно, куча не подходит для вашего прецедента, если вам нужно часто извлекать узлы из середины.
(для минимальной кучи вы можете, очевидно, использовать int.MinValue или -inf или что-то еще)
То, что вы хотите достичь, - это не типичная операция кучи, и мне кажется, что когда вы вводите "удалить средний элемент" в качестве метода, лучше выбрать другое двоичное дерево (например, красно-черное или AVL-дерево). У вас есть красно-черное дерево, реализованное на некоторых языках (например, карта и набор в С++).
В противном случае способ удаления среднего элемента будет предложен в ответе rejj: присвойте этому элементу большое значение (для максимальной кучи) или небольшое значение (для кучи min), просеите его до тех пор, пока он не станет root, а затем удалите его,
Этот подход по-прежнему сохраняет сложность O (log (n)) для удаления среднего элемента, но тот, который вы предлагаете, делает. Он будет иметь сложность O (n * log (n)), и поэтому это не очень хорошо. Надеюсь, что это поможет.