WikiDer > Beap

А бить, или же двупородный куча, это структура данных где узел обычно имеет двух родителей (если он не является первым или последним на уровне) и двух дочерних узлов (если только он не находится на последнем уровне). В отличие от кучи, beap позволяет сублинейный поиск. Бип был представлен Ян Манро и Хендра Суванда. Связанная структура данных - это Молодая картина.

Beap

Спектакль

Высота конструкции примерно ${ displaystyle { sqrt {n}}}$. Кроме того, если последний уровень заполнен, количество элементов на этом уровне также будет ${ displaystyle { sqrt {n}}}$. Фактически, благодаря этим свойствам все основные операции (вставка, удаление, поиск) выполняются в ${ displaystyle O ({ sqrt {n}})}$ время в среднем. Найти операции в куче можно ${ Displaystyle О (п)}$ в худшем случае. Удаление и вставка новых элементов включает перемещение элементов вверх или вниз (как в куче) для восстановления инварианта beap. Дополнительным преимуществом является то, что beap обеспечивает постоянный доступ по времени к самому маленькому элементу и ${ displaystyle O ({ sqrt {n}})}$ время для максимального элемента.

Собственно, ${ displaystyle O ({ sqrt {n}})}$ Операция find может быть реализована, если поддерживаются родительские указатели на каждом узле. Вы должны начать с самого нижнего элемента верхнего узла (аналогично крайнему левому дочернему элементу в куче) и перемещаться вверх или вправо, чтобы найти интересующий элемент.

Рекомендации

• Манро, Дж. Ян; Суванда, Хендра (1980). «Неявные структуры данных для быстрого поиска и обновления». Журнал компьютерных и системных наук. 21 (2): 236–250. Дои:10.1016/0022-0000(80)90037-9.
• Уильямс, Дж. У. Дж. (Июнь 1964 г.). «Алгоритм 232 - Heapsort». Коммуникации ACM. 7 (6): 347–348. Дои:10.1145/512274.512284.