K-D куп

KD купDing Y., Weiss M.A. (1993) The K-D heap: An efficient multi-dimensional priority queue. In: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg е податочна структура во компјутерската наука која што имплементира  повеќедимензионална приоритетна редица без да бара дополнителен простор. Тоа претставува генерализација на грамадата.Advanced Data Structures, Peter Brass, , page 270 Овозможува ефикасно вметнување, пребарување на минималниот елемент и бришење на минималниот елемент во која било  димензија k, и затоа вклучува двојно завршна приоритетна редица како посебен случај.

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

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

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

 Јазолот во коренот има најмало 1-то својство од целото дрво и
 Секој друг јазол v што не е корен, е таков што ако неговиот родител w го има најмалиот i-ти својство на поддрвото вкоренето од родителот, тогаш v го има најмалиот  -тото својство на целото под дрво вкоренето од v.

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

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

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

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

 Наводи 

Категорија:Податочни структури
Категорија:Информатика