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

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

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

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

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

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

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

Поиск элемента в куче – это операция 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 

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

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

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

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

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

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

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

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

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

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

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

  • Как увеличить размер кучи приложения в Eclipse?
  • Используются ли примитивы Java в стеке или куче?
  • Поля classа, хранятся ли они в стеке или куче?
  • Распределение памяти: стек против кучи?
  • Android: BitmapFactory.decodeStream () из памяти с файлом 400 КБ с бесплатной кучей 2 МБ
  • java.lang.OutOfMemoryError: превышен верхний предел GC
  • Где находится ссылка на переменную, в стеке или в куче?
  • Критику моего неинтрузивного отладчика кучи
  • Как определяется размер кучи Java по умолчанию?
  • Как предотвратить создание объекта в куче?
  • Создание объекта в стеке / куче?
  • Давайте будем гением компьютера.