Удаление в двоичную кучу - PullRequest
Новая
       28

Удаление в двоичную кучу

6 голосов
/ 28 сентября 2011

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

Но по следующей ссылке написано недоступно:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

                Binary Search  AVL Tree   Binary Heap (min)  Binomial Queue (min)

Find            O(log n)       O(log n)   unavailable         unavailable
Delete element  O(log n        O(log n)   unavailable         unavailable

Я немного смущен этим.

Заранее благодарим за все разъяснения.

Ответы [ 3 ]

3 голосов
/ 28 сентября 2011

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

  • find-element, O (1) ожидаемое время с хеш-таблицей
  • клавиша уменьшения меньше минимума, O (lg n ) время
  • delete-min и обновить хэш-таблицу, O (lg n ) объединенное ожидаемое время.
2 голосов
/ 27 марта 2012

Возможно регулярное удаление, как DeleteMin / Max. «Проблема» заключается в том, что вы должны проверить как на повышение, так и на понижение (т. Е. Когда «последний» узел занимает вакантное место, он может быть переоценен или недооценен. Поскольку для очевидного причины, это легко проверить на правильность.

Единственная проблема, которая остается, - это Находка. Ответ выше гласит, что вы можете найти элемент в O (LG N), но я не знаю, как. В моих реализациях я обычно строю кучу указателей на элементы, а не на элементы (более дешевое копирование при повышении / понижении). Я добавляю переменную "position" к типу Element, которая отслеживает индекс указателя элемента в куче. Таким образом, учитывая элемент E, я могу найти его положение в куче за постоянное время.

Очевидно, что это не вырезано для каждой реализации.

0 голосов
/ 31 января 2018

Я запутался, почему операция удаления двоичной кучи упоминается как недоступная в ссылке вашего вопроса.Удаление в двоичную кучу вполне возможно и состоит из двух других операций двоичной кучи.https://en.wikipedia.org/wiki/Binary_heap

Я считаю, что вы знаете все другие операции Binary Heap

Для удаления ключа из двоичной кучи требуется 2 строки кода / операции.Предположим, вы хотите удалить элемент с индексом x.Уменьшите его значение до минимально возможного целого числа.Это Integer.MIN_VALUE.Так как это самое низкое значение из всех целых, оно перейдет в корневую позицию, когда выполнение decreaseItem(int index, int newVal) будет завершено.Затем извлеките корень, вызвав метод extractMin(). 

// Complexity: O(lg n)
public void deleteItem(int index) {
    // Assign lowest value possible so that it will reach to root
    decreaseItem(index, Integer.MIN_VALUE);
    // Then extract min will remove that item from heap tree. correct ?
    extractMin();
}

Полный код: BinaryHeap_Demo.java

...