Halda K-D - K-D heap

Halda K-D[1] je datová struktura v počítačová věda který implementuje vícerozměrný prioritní fronta bez nutnosti dalšího prostoru. Jedná se o zobecnění Halda.[2] Umožňuje efektivní vložení, dotaz na minimální prvek a odstranění minimálního prvku v kterékoli z dimenzí k, a proto zahrnuje oboustranná hromada jako zvláštní případ.
Struktura
Vzhledem ke sbírce n položky, kde každý má klíče (nebo priority), hromada K-D je uspořádá do a binární strom který splňuje dvě podmínky:
- Je to kompletní binární strom, což znamená, že je plná až na poslední vrstvu, kde musí být vyplněna zleva.
- To uspokojuje objednávka haldy k-d.
Vlastnost objednávka haldy k-d je analogický jako u halda vlastnost pro běžné hromady. Hromada udržuje pořadí haldy k-d, pokud:
- Uzel v kořenovém adresáři má nejmenší 1. vlastnost celého stromu a
- Každý druhý uzel proti to není kořen, je takový, že pokud je jeho rodič w má tedy nejmenší i-tu vlastnost podstromu zakořeněného rodičem proti má nejmenší -tá vlastnost celého podstromu zakořeněného proti.
Jedním z důsledků této struktury je, že nejmenší první prvek vlastnosti bude triviálně v kořenovém adresáři a navíc všechny nejmenší i-té prvky vlastností pro každého i bude v první k úrovně.
Operace
Vytváření hromady K-D z n položky trvá Na) čas. Jsou podporovány následující operace:
- Vložte novou položku včas O (log n)
- Načtěte položku s minimálním klíčem v libovolné dimenzi v konstantním čase
- Odstraňte položku s minimálním klíčem v jakékoli dimenzi v čase O (log n)
- Odstraňte nebo upravte libovolnou položku v hromadě včas O (log n) za předpokladu, že je známa jeho poloha v haldě
Důležité je, že skrytá konstanta v těchto operacích je exponenciálně velká relativní , počet rozměrů, takže hromady K-D nejsou praktické pro aplikace s velmi mnoha rozměry.
Reference
- ^ Ding Y., Weiss M.A. (1993) The K.-D halda: Efektivní vícerozměrná prioritní fronta. In: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, sv. 709. Springer, Berlin, Heidelberg
- ^ Pokročilé datové struktury, Peter Brass, ISBN 978-0-521-88037-4, strana 270