¿Encontrando el valor mínimo del grupo máximo?

Question

Definir un elemento por tener:

• 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| < delta ⇒ a 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?

Answer 1

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.

Answer 2

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!