K-D куча - K-D heap

Двумерная куча с 20 элементами.

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

Структура

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

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

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

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

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

Операции

Создание кучи K-D из п предметы принимает На) время. Поддерживаются следующие операции:

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

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

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