Как удалить в кучу структуру данных?

Question

Я понимаю, как удалить корневой узел из максимальной кучи, но является ли процедура удаления узла из середины для повторного удаления и замены корневого узла до тех пор, пока не будет удален нужный узел?

1. Является ли O (log n) оптимальной сложностью для этой процедуры?

2. Влияет ли это на большую сложность O, так как другие узлы должны быть удалены для удаления определенного узла?

Answer 1

На самом деле вы можете без проблем удалить элемент из середины кучи.

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

Это процедура для максимальной кучи.Конечно, за минимальную кучу вы должны поменять местами большие и меньшие случаи.

Поиск элемента в куче - операция O (n), но если вы уже знаете, гдеон находится в куче, удаляя его O (log n).

Несколько лет назад я опубликовал очередь приоритетов на основе кучи для DevSource.См. Реализация приоритетной очереди в C # .У него есть RemoveAt метод, который делает именно то, что я описал.

Полный источник в http://www.mischel.com/pubs/priqueue.zip

Обновление

Некоторые спрашивали, возможно ли подняться послеперемещение последнего узла в куче для замены удаленного узла.Рассмотрим эту кучу:

        1
    6       2
  7   8   3

Если вы удалите узел со значением 7, значение 3 заменит его:

        1
    6       2
  3   8

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

        1
    3       2
  6   8

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

Answer 2

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

В куче поиск произвольного элемента равен O(n), поэтому удаление элемента [если задано значением] также равно O(n).

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

Если ваш элемент задан ссылкой, его можно удалить в O(logn), просто «заменив» его последним листом [помните, что куча реализована как полное двоичное дерево, поэтому есть последний лист и вы точно знаете, где он находится], удалите эти элементы и заново накапливайте соответствующие подпучки.

Answer 3

Если у вас есть максимальная куча, вы можете реализовать это, назначив значение, большее, чем любое другое (например, что-то вроде int.MaxValue или inf на каком бы языке вы не использовали), возможному для удаляемого элемента, затем -heapify, и это будет новый корень. Затем выполните регулярное удаление корневого узла.

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

(для минимальной кучи вы можете явно использовать int.MinValue или -inf или что-то еще)

Answer 4

То, чего вы хотите достичь, не является типичной операцией кучи, и мне кажется, что, как только вы введете «удалить средний элемент» в качестве метода, лучше выбрать другое двоичное дерево (например, красно-черное или дерево AVL). В некоторых языках реализовано красно-черное дерево (например, map и установлено в c ++).

В противном случае способ удаления среднего элемента такой же, как предложено в ответе Рейджа: назначьте элементу большое значение (для максимальной кучи) или небольшое значение (для минимальной кучи), просейте его до корневого уровня и затем удалите его ,

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