K-D куп

2-d грамада со 20 елементи.

KD куп е податочна структура во компјутерската наука која што имплементира повеќедимензионална приоритетна редица без да бара дополнителен простор. Тоа претставува генерализација на грамадата. Овозможува ефикасно вметнување, пребарување на минималниот елемент и бришење на минималниот елемент во која било димензија k, и затоа вклучува двојно завршна приоритетна редица како посебен случај.

Структура

Дадена е колекција од n ставки, каде што секоја има $k$ клучеви (или приоритети), купот K-D ги организира нив во бинарно дрво што исполнува два услови:

• Тоа е целосно бинарно дрво, што значи дека е полно, освен евентуално последниот слој, каде што мора да се наполни одлево.
• Го задоволува редоследот на купишта k-d.

Својството на редоследот на купишта k-d е аналогно на големиот имот за редовни купишта. Купиште одржува редослед на k-d купишта ако:

• Јазолот во коренот има најмало 1-то својство од целото дрво и
• Секој друг јазол v што не е корен, е таков што ако неговиот родител w го има најмалиот i-ти својство на поддрвото вкоренето од родителот, тогаш v го има најмалиот $(i\mod k)+1$ -тото својство на целото под дрво вкоренето од v.

Една од последиците од оваа структура е тоа дека најмалиот 1-во својствен елемент тривијално ќе биде во коренот, а додатно на тоа сите најмали елементи со i-тото својство, за секое i ќе бидат во првите k нивоа.

Операции

Создавањето на K-D куп од n трае O(n) време. Поддржани се следниве операции:

• Вметнете нова ставка во време О (log n)
• Вратете го предметот со минимален клуч во која било од димензиите во константно време
• Избришете ставка со минимален клуч во која било димензија во времето О (log n)
• Избришете или изменете произволна ставка во грамада со време O (log n) под претпоставка дека е позната нејзината позиција во грамада

Многу е важно, дека скриената константа во овие операции е релативно експоненцијално-голема $k$, бројот на димензии, така што купиштата K-D не се практични за апликации со многу многу димензии.