montón KD
Un montón 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.
Dada una colección de n elementos, donde cada uno tiene claves (o prioridades), el montón KD los organiza en un árbol binario que satisface dos condiciones:
La propiedad del orden del montón kd es análoga a la propiedad del montón para los montones normales. Un montón mantiene el orden del montón kd si:
Una consecuencia de esta estructura es que el elemento de propiedad 1-st más pequeño estará trivialmente en la raíz y, además, todos los elementos de propiedad i -th más pequeños para cada i estarán en los primeros k niveles.
Es importante destacar que la constante oculta en estas operaciones es exponencialmente grande en relación con el número de dimensiones, por lo que los montones KD no son prácticos para aplicaciones con muchas dimensiones.
