Попробуйте понять delete-min Min-Max Heap - PullRequest
Новая
       17

Попробуйте понять delete-min Min-Max Heap

0 голосов
/ 21 декабря 2018

Я хочу понять, как работает процесс удаления кучи min-max, я искал его псевдокод, но ничего не нашел, и кажется, что я не могу попросить псевдокод здесь.Итак, вот моя проблема

g0

Может кто-нибудь показать логику "удаления минимального элемента 7", по крайней мере, дайте мне знать, как псевдокод "чувствует себя"?

Редактировать: Если люди думают, что я ничего не пробую, вот еще один слайд:

  1. [1.1] НадеюсьНе понимаю:

    (4-я строка): ... а затем вставьте в кучу мин-макс.

    Вызывает ли здесь « reinsert » оригинальную процедуру вставки?Или это просто означает случаи, следующие за ним?

    [1.2]

    (8-я строка): Наименьший ключ в min.Максимальная куча - один из детей или внуков корня.

    Я не уверен, что " внуков "рекурсивно включает своих внуков.

    Слайд: g1

Я могу понять процедуру" VerifyMax ", используемую при вставке, не уверен, что этопроцедура будет использоваться при удалении ...:

enter image description here

Ответы [ 3 ]

0 голосов
/ 21 декабря 2018

  1. Замените "7" на "90" (замена элемента min последним элементом) и уменьшите размер кучи min-max.

  2. Swap "90 "с" 9 "(так как сейчас это минимум).Теперь «9» является корнем.

  3. Поменяйте «90» на «70», так как свойство max heap нарушено.

  4. Swap "70"с" 20 "в качестве минимального свойства кучи нарушается.Это конечный результат.

0 голосов
/ 22 декабря 2018

Теперь я очень уверен, что путаница после понимания кучи min-max:

  1. Это не то же самое, что и оригинальный insert метод кучи min-max

  2. Это означает именно внука, а не рекурсивно.Поскольку внук находится на минимальном уровне.

0 голосов
/ 21 декабря 2018

Алгоритм похож на процедуру DeleteMin обычной min-heap (или процедуру DeleteMax для max-heap):

  1. Заменить текущий min (то есть первый элементв куче) с последним элементом в куче.
  2. Уменьшите размер кучи на единицу.
  3. Используйте процедуру TrickleDown для первого элемента, чтобы восстановить свойство кучи.

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

...