Бип

Бип сублинейном , или двуродительская куча , — это структура данных для набора (или карты, или мультимножества, или мультикарты), которая позволяет находить, вставлять или удалять элементы (или отображения) в времени . В бипе каждый элемент хранится в узле, имеющем до двух родительских и до двух дочерних элементов, причем значение родительского узла никогда не превышает значение любого из его дочерних элементов.

Beaps реализуются с использованием массива, содержащего только значения, подлежащие сохранению, при этом отношения родитель-потомок определяются неявно индексами массива. (То есть: бипы представляют собой неявную структуру данных .) В этом отношении они похожи на двоичные кучи , которые обычно также реализуются таким же образом. Однако их ТТХ отличаются от кучи; в частности, бип обеспечивает сублинейный поиск произвольных элементов.

Бип представили Ян Манро и Хендра Суванда . Связанная структура данных — это таблица Юнга .

Производительность

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

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

Ссылки

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