Куча, просачивающийся метод

В настоящее время я делаю max-heap. Когда я использую метод remove(), я понимаю, что поменяюсь местами с более крупными дочерними элементами. Что делать, если оба ребенка имеют одинаковый приоритет? например

Дело 1:

куча = [5,7,7,16,15]

если я уберу 5 и заменю его на 15, я буду просачиваться вправо (что неправильно), поэтому я буду просачиваться в левую сторону.

но используя ту же логику, если у меня есть

куча = [5,7,7,16,15,18]

и я стекаю влево, это уже не будет действительной кучей.

Что я могу сделать, чтобы убедиться, что у меня есть допустимая куча?


heap max-heap
person Sugihara    schedule 24.05.2013    source источник
comment
Как это максимальная куча? Если 5 — верхний элемент, разве это не минимальная куча?   -  person Patashu    schedule 24.05.2013

Ответы (1)


arrow_upward
0
arrow_downward

Неважно.

Стекание вправо в первом случае нормально:

[15, 7, 7, 16] -> [7, 7, 15, 16]

Стекание влево в первом случае нормально:

[15, 7, 7, 16] -> [7, 15, 7, 16]

Стекание вправо во втором случае нормально:

[18, 7, 7, 16, 15] -> [7, 7, 18, 16, 15]

Стекание влево во втором случае нормально:

[18, 7, 7, 16, 15] -> [7, 18, 7, 16, 15] -> [7, 15, 7, 16, 18]

person Stefan Haustein    schedule 24.05.2013