КД куча

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

Структура

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

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

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

Узел в корне имеет наименьшее 1-е свойство всего дерева, и
Любой другой узел v, не являющийся корнем, таков, что если его родительский элемент w имеет наименьшее i-е свойство поддерева, корнем которого является родительский узел, то v имеет наименьшее i-е свойство поддерева, корнем которого является родительский узел. $(i\mod k)+1$ -е свойство всего поддерева с корнем v.

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

Операции

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

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

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

Ссылки

^ Дин Ю., Вайс М.А. (1993) Куча K -D: эффективная многомерная очередь с приоритетами. В: Дене Ф., Сак-младший, Санторо Н., Уайтсайдс С. (ред.) Алгоритмы и структуры данных. WADS 1993. Конспекты лекций по информатике, том 709. Springer, Берлин, Гейдельберг.
^ Расширенные структуры данных, Питер Брасс, ISBN 978-0-521-88037-4 , стр. 270

[1] Дин Ю., Вайс М.А. (1993) Куча K -D: эффективная многомерная очередь с приоритетами. В: Дене Ф., Сак-младший, Санторо Н., Уайтсайдс С. (ред.) Алгоритмы и структуры данных. WADS 1993. Конспекты лекций по информатике, том 709. Springer, Берлин, Гейдельберг.

[2] Расширенные структуры данных, Питер Брасс, ISBN 978-0-521-88037-4 , стр. 270

[1]

[2]