Преглед на кодот на K-D куп

[[Податотека:K-d_heap_2_keys.png|мини| 2-d грамада со 20 елементи.]]
KD куп<ref>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</ref> е податочна структура во [[Информатика|компјутерската наука]] која што имплементира  повеќедимензионална [[Приоритетен ред|приоритетна редица]] без да бара дополнителен простор. Тоа претставува генерализација на грамадата.<ref>Advanced Data Structures, Peter Brass, {{ISBN|978-0-521-88037-4}}, page 270</ref> Овозможува ефикасно вметнување, пребарување на минималниот елемент и бришење на минималниот елемент во која било  димензија k, и затоа вклучува [[Двојна завршна приоритетна редица|двојно завршна приоритетна редица]] како посебен случај.

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

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

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

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

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

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

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

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

== Наводи ==
{{Наводи}}
[[Категорија:Податочни структури]]
[[Категорија:Информатика]]