5

Definir un elemento por tener:¿Encontrando el valor mínimo del grupo máximo?

  • un identificador único
  • un valor
  • un tiempo de creación
  • una deleción tiempo

he dos flujos de entrada - uno que me informa cuando se crea un elemento, uno que me informa cuando se elimina el elemento. Llamar a un elemento que ha sido creado pero no destruido "vivo".

que puede realizar un seguimiento del valor máximo de todos los elementos vivos utilizando una pila:

whenCreated(item): 
    i = heap.size 
    heap-up(item, heap.size) 
    heap.size = heap.size + 1 
    max-value = heap[0] 

whenDeleted(item): 
    ktem = heap[heap.size - 1] 
    heap.size = heap.size - 1 
    heap-up(ktem, index[item.id]) 
    heap-down(ktem, index[ktem.id]) 
    max-value = heap[0] 

heap-up(item, i): 
    while (i > 0): 
    j = floor((i-1)/2) 
    jtem = heap[j] 
    if (jtem.value > item.value): 
     break while 
    index[jtem.id] = i 
    heap[i] = heap[i] 
    i = j 
    index[item.id] = i 
    heap[i] = item 

heap-down(item, i): 
    while (2*i + 1 < heap.size): 
    if (2*i + 1 == heap.size or heap[2*i+1].value > heap[2*i+2].value): 
     j = 2*i + 1 
    else 
     j = 2*i + 2   
    jtem = heap[j] 
    if (jtem.value < item.value): 
     break while 
    index[jtem.id] = i 
    heap[i] = heap[i] 
    i = j   
    index[item.id] = i 
    heap[i] = item 

Si Tengo n artículos, a continuación, añadiendo o eliminando uno toma O(log n) tiempo.

Supongamos ahora que los artículos se agrupan de tal manera que da dos artículos, a y b, |a.value - b.value| < deltaa y b están en el mismo grupo.

Por ejemplo, si tenemos los valores (1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16) y delta = 2, a continuación, los racimos son (1, 2, 3, 4), (7, 8), (11) y (13, 14, 15, 16).

Me gustaría realizar un seguimiento del valor mínimo del clúster que contiene el valor de vida máximo. Puedo hacer esto leyendo valores del montón en orden hasta que encuentre un espacio entre valores de tamaño mayor que igual a delta. Sin embargo, esto toma el tiempo O(n), que parece bastante ineficaz.

¿Hay un algoritmo O(log n) para rastrear el valor mínimo de ese clúster?

+0

¿Los clústeres son transitivos? Por ejemplo, si el delta es 2, ¿1, 2, 3, 4, 5 y 6 están todos en el mismo grupo? – templatetypedef

+0

Dudo que puedas hacerlo solo con tu montón actual. Parece que necesitará una estructura de datos separada para hacer esto de manera eficiente. Un conjunto disjunto sería bueno, aunque sus clústeres pueden fusionarse y luego desaparecer, por lo que necesita algo que permita la separación (lo que no ocurre con la unión-unión), también conocido como el refinamiento de la partición. – davin

+0

La respuesta de templatetypedef funciona, aunque parece una implementación difícil. Si no anticipa muchos casos dudosos, tal vez valga la pena la simple solución 'O (n)'. Es decir, si será raro que el final del clúster cambie a menudo, entonces no es el fin del mundo. Puedes mejorarlo ligeramente moviéndote a BST y manteniendo un único puntero, y luego tu trabajo 'O (n)' no ocurre en delete, solo en inserts e incluso entonces, si esperas pequeños clusters relativos a 'n' no debería ser notable. – davin

Respuesta

0

Puede usar árboles binarios (o sus variantes) en lugar de montones. Encontrar un valor y un valor mínimo están ambos en O (logn). Construya árboles binarios separados para cada grupo.

No estoy seguro de cómo se realiza la agrupación (puede construir varios clústeres que satisfagan la condición delta que menciona. ¿Por qué eligió esta agrupación en particular?). También puede considerar tener un árbol gigante de búsqueda binaria para almacenar todos los valores y designar algunos de los nodos como "cabezales de clúster" (es decir, los elementos del subárbol que contiene este nodo son un clúster). De esta manera, debería ser capaz de crear y eliminar nuevos clusters fácilmente.

+0

No estoy seguro de ver cómo esto ayuda cuando se tiene en cuenta la agrupación. ¿Cómo determinaría de manera eficiente si dos nodos están en el mismo clúster? – templatetypedef

+0

¿Qué sucede si necesita unir dos clusters? ¿O dividir un clúster en dos? – templatetypedef

+0

@templatetypedef Crea un árbol separado para cada grupo. – ElKamina

4

Creo que puede hacer esto utilizando un árbol de búsqueda binaria equilibrado de árboles de separación para garantizar el tiempo amortizado O (log n) para cada operación.

Supongamos que no estamos haciendo ningún agrupamiento. En ese caso, podría simplemente almacenar todos los elementos en un árbol de búsqueda binaria equilibrado para obtener la inserción, eliminación y búsqueda-min de O (log n). Pero con la agrupación, esto cambia. Mi sugerencia es mantener un BST de los clusters ordenados por el rango de valores que se mantienen en el clúster, donde cada clúster se representa como un árbol desplegable de los nodos que contiene.

Para insertar un elemento en la estructura de datos, realice una búsqueda en el BST para el predecesor y sucesor del elemento en cuestión. Si el nodo no pertenece a ninguno de estos clústeres, cree un árbol de selección singleton fuera de ese nodo e insértelo en el BST.Si está contenido exactamente en uno de los dos clústeres que encontró, insértelo en ese clúster. Si está contenido en ambos clústeres, elimine ambos clústeres del BST, combínelos en un solo clúster, inserte el nuevo nodo en ese clúster y luego reinserte el clúster en el BST. El tiempo de búsqueda en todos los casos en O (log n) para encontrar los dos clústeres, luego O (log n) amortizó el tiempo para insertarlo en un clúster. Combinar dos árboles de separación es realmente rápido aquí; dado que los clusters no se fusionaron antes, un árbol contiene valores que son todos estrictamente mayores que todos los valores en el otro árbol, por lo que la fusión se puede hacer en O (log n) tiempo amortizado mediante el retiro de punteros. El costo de eliminar los dos árboles y volver a agregarlos también es O (log n).

Para encontrar el valor mínimo del clúster máximo, busque el clúster máximo en el BST en el tiempo O (log n), luego encuentre el elemento mínimo del clúster que encuentre en el tiempo amortizado O (log n).

Para eliminar un elemento, busque el clúster que lo contiene en el tiempo O (log n). Si está en su propio clúster, elimine ese clúster Fromm del árbol. De lo contrario, elimine el elemento del clúster en el que se encuentra, luego encuentre su predecesor y su sucesor dentro de ese clúster. Si están dentro del delta del otro, entonces el clúster todavía está bien y hemos terminado. De lo contrario, el clúster debe estar dividido. En O (log n) tiempo amortizado, divida el clúster en el grupo de nodos menor o igual que el predecesor y mayor o igual que el sucesor, luego vuelva a insertar ambos clústeres en el árbol.

En general, esto da O (log n) amortizado para cada operación.

Espero que esto ayude!

+0

¡Echaré un vistazo a los árboles abiertos, gracias! – rampion

Cuestiones relacionadas