Куча КД

Куча KD ^[1] — это структура данных в информатике , которая реализует многомерную приоритетную очередь без необходимости дополнительного пространства. Это обобщение кучи . [ ^2] Она позволяет эффективно вставлять, запрашивать минимальный элемент и удалять минимальный элемент в любом из k измерений, и поэтому включает двухстороннюю кучу как особый случай.

Учитывая набор из n элементов, каждый из которых имеет ключи (или приоритеты), куча KD организует их в двоичное дерево , которое удовлетворяет двум условиям:${\displaystyle к}$

• Это полное бинарное дерево , то есть оно заполнено, за исключением, возможно, последнего слоя, который должен быть заполнен слева.
• Он удовлетворяет порядку кучи kd.

Свойство порядка кучи kd аналогично свойству кучи для обычных куч. Куча поддерживает порядок кучи kd, если:

• Узел в корне имеет наименьшее 1-е свойство всего дерева, и
• Каждый другой узел v, не являющийся корнем, таков, что если его родительский узел w имеет наименьшее i-е свойство поддерева, корнем которого является родительский узел, то v имеет наименьшее -е свойство всего поддерева, корнем которого является v.${\displaystyle (i\mod k)+1}$

Одним из следствий этой структуры является то, что наименьший 1-й элемент свойства будет тривиально находиться в корне, и, более того, все наименьшие i -е элементы свойства для каждого i будут находиться на первых k уровнях.

Создание кучи KD из n элементов занимает O(n) времени. Поддерживаются следующие операции:

• Вставить новый элемент за время O(log n)
• Извлечь элемент с минимальным ключом в любом из измерений за постоянное время
• Удалить элемент с минимальным ключом в любом измерении за время O(log n)
• Удалить или изменить произвольный элемент в куче за время O(log n), предполагая, что его положение в куче известно

Важно отметить, что скрытая константа в этих операциях экспоненциально велика относительно числа измерений, поэтому кучи KD непрактичны для приложений с очень большим количеством измерений.${\displaystyle к}$