Рубрики

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 47

Оператор delete (i) для структуры данных двоичной кучи должен быть предназначен для удаления элемента в i-м узле. Предположим, что куча реализована в массиве, а i ссылается на i-й индекс массива. Если дерево кучи имеет глубину d (количество ребер на пути от корня до самого дальнего листа), то какова сложность времени для эффективного исправления кучи после удаления элемента?
(A) O (1)
(B) O (d), но не O (1)
(C) O (2 d ), но не O (d)
(D) O (d2 d ), но не O (2 d )

Ответ: (Б)
Объяснение:

Для этого вопроса нам нужно немного изменить операцию delete_min () структуры данных кучи, чтобы реализовать операцию delete (). Идея состоит в том, чтобы очистить место в массиве по индексу i (позиции, в которой должен быть удален элемент) и заменить его последним листом в куче (помните, что куча реализована как полное двоичное дерево, чтобы вы знали местоположение последний лист), уменьшите размер кучи и теперь, начиная с текущей позиции (позиции, в которой был удален элемент, который мы удалили), сдвиньте его вверх в случае, если новый замененный элемент больше, чем родительский элемент старого элемента (учитывая max-heap). Если это не больше, чем родитель, тогда сверните это вниз, сравнивая с ценностью ребенка. Вновь добавленный элемент может просачиваться вверх / вниз максимум в d раз, что является глубиной структуры данных кучи.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 47

0.00 (0%) 0 votes