Un montón de KD [1] es una estructura de datos en informática que implementa una cola de prioridad multidimensional sin requerir espacio adicional. Es una generalización del montón . [2] Permite la inserción eficiente, la consulta del elemento mínimo y la eliminación del elemento mínimo en cualquiera de las k dimensiones y, por lo tanto, incluye el montón de dos extremos como un caso especial.
Estructura
Dada una colección de n elementos, donde cada uno tieneclaves (o prioridades), el montón de KD las organiza en un árbol binario que satisface dos condiciones:
- Es un árbol binario completo , lo que significa que está lleno excepto posiblemente la última capa, donde debe llenarse desde la izquierda.
- Satisface el orden del montón de kd.
La propiedad de kd heap order es análoga a la propiedad de heap para montones regulares. Un montón mantiene el orden del montón de kd si:
- El nodo en la raíz tiene la primera propiedad más pequeña de todo el árbol, y
- Cualquier otro nodo v que no sea la raíz, es tal que si su padre w tiene la propiedad i-ésima más pequeña del subárbol enraizado por el padre, entonces v tiene la más pequeña-ésima propiedad de todo el subárbol enraizado por v.
Una consecuencia de esta estructura es que el primer elemento de propiedad más pequeño estará trivialmente en la raíz y, además, todos los elementos de propiedad i -ésimo más pequeños para cada i estarán en los primeros k niveles.
Operaciones
Crear un montón de KD a partir de n elementos lleva O (n) tiempo. Las operaciones siguientes son compatibles:
- Insertar un nuevo elemento en el tiempo O (log n)
- Recuperar el artículo con clave mínima en cualquiera de las dimensiones en tiempo constante
- Eliminar un elemento con una clave mínima en cualquier dimensión en el tiempo O (log n)
- Eliminar o modificar un elemento arbitrario en el montón en el tiempo O (log n) asumiendo que se conoce su posición en el montón
Es importante destacar que la constante oculta en estas operaciones es exponencialmente grande relativa , el número de dimensiones, por lo que los montones KD no son prácticos para aplicaciones con muchas dimensiones.
Referencias
- ^ Ding Y., Weiss MA (1993) Elmontón de K- D: una cola de prioridad multidimensional eficiente. En: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algoritmos y estructuras de datos. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlín, Heidelberg
- ^ Estructuras de datos avanzadas, Peter Brass, ISBN 978-0-521-88037-4 , página 270