БЕАП или би-родительских кучи , является структура данных , когда узел , как правило , имеет двух родителей (если он не является первым или последним на уровне) и двое детей (если только она не находится на последнем уровне). В отличие от кучи, beap позволяет выполнять сублинейный поиск. Бип был представлен Яном Манро и Хендрой Сувандой . Связанная структура данных - таблица Юнга .
Представление
Высота конструкции примерно . Кроме того, предполагая, что последний уровень заполнен, количество элементов на этом уровне также будет. Фактически, благодаря этим свойствам все основные операции (вставка, удаление, поиск) выполняются ввремя в среднем. Найти операции в куче можнов худшем случае. Удаление и вставка новых элементов включает перемещение элементов вверх или вниз (как в куче) для восстановления инварианта beap. Дополнительным преимуществом является то, что beap обеспечивает постоянный доступ по времени к наименьшему элементу и время для максимального элемента.
Собственно, Операция find может быть реализована, если поддерживаются родительские указатели на каждом узле. Вы должны начать с самого нижнего элемента верхнего узла (аналогично крайнему левому дочернему элементу в куче) и перемещаться вверх или вправо, чтобы найти интересующий элемент.
Рекомендации
- Манро, Дж. Ян; Суванда, Хендра (1980). «Неявные структуры данных для быстрого поиска и обновления». Журнал компьютерных и системных наук . 21 (2): 236–250. DOI : 10.1016 / 0022-0000 (80) 90037-9 .
- Уильямс, JWJ (июнь 1964 г.). «Алгоритм 232 - Heapsort». Коммуникации ACM . 7 (6): 347–348. DOI : 10.1145 / 512274.512284 .