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

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

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

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

4 Solutions collect form web for “Как удалить в структуре данных кучи?”

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

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

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

Поиск элемента в куче – это операция 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)), и поэтому это не очень хорошо. Надеюсь, это поможет.

  • Есть ли способ снизить кучу Java, когда он не используется?
  • Размер кучи Android на разных телефонах / устройствах и версиях ОС
  • g ++ размер массива без предупреждения?
  • Создание объекта в стеке / куче?
  • Критику моего неинтрузивного отладчика кучи
  • Используются ли примитивы Java в стеке или куче?
  • Когда выделены векторы, они используют память в куче или стеке?
  • Недопустимый адрес кучи и фатальный сигнал 11
  • Почему программисты C ++ минимизируют использование «новых»?
  • Распределение памяти: стек против кучи?
  • Как найти количество объектов в куче
  • Interesting Posts

    Что такое инструмент для получения полного каталога / списка файлов с подробной информацией, включая хеш (ы)?

    Удалить все строки, начинающиеся с # из файла

    Почему диски CD / DVD не могут быть разделены?

    DD-WRT, переадресация виртуального хоста другим именам / IP-адресам с использованием циклического шифрования

    Какой инструмент может дать мне почасовое напоминание?

    Какие методы «clearfix» можно использовать?

    Как вы вызываете msdeploy из powershell, когда параметры имеют пробелы?

    o отобразить изображение

    Автоматическое изменение размера javafx и добавление кнопок

    Как я могу получить и использовать заголовочный файл в моей программе на C ++?

    Знаю ли я, нужен ли мне Multi-Dex? (ClassNotFoundException)

    VirtualBox: Windows 7 говорит, что это не настоящая

    Что делает оператор?

    Как добавить загрузчик даты Picker Bootstrap 3 в проекте MVC 5 с использованием механизма Razor?

    Тайм-аут Spring RestTemplate

    Давайте будем гением компьютера.