Trovare il valore minimo del cluster massimo?

Question

Definire un oggetto come avente:

• un ID univoco
• un valore
• un tempo di creazione
• una delezione tempo

ho torrenti due ingressi - uno che mi informa quando viene creato un articolo, uno che mi informa quando l'oggetto viene cancellato. Chiama un oggetto che è stato creato ma non distrutto "vivente".

faccio a monitorare il valore massimo di tutti gli elementi che vivono con un mucchio:

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 

Se ho n voci, poi aggiungendo o eliminando uno prende O(log n) volta.

Ora supponiamo gli elementi sono raggruppati in modo tale che dato due elementi, a e b, |a.value - b.value| < delta ⇒ a e b sono nello stesso cluster.

Per esempio, se abbiamo i valori (1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16) e delta = 2, poi i grappoli sono (1, 2, 3, 4), (7, 8), (11) e (13, 14, 15, 16).

Vorrei tracciare il valore minimo del cluster che contiene il valore di vita massimo. Posso farlo leggendo i valori dall'heap in ordine finché non trovo uno spazio tra i valori di dimensione maggiore di uguale a delta. Tuttavia, questo richiede tempo O(n), che sembra piuttosto inefficace.

Esiste un algoritmo O(log n) per tracciare il valore minimo di tale cluster?

Answer 1

È possibile utilizzare gli alberi binari (o le sue varianti) anziché gli heap. Trovare un valore e un valore minimo sono entrambi in O (logn). Costruisci alberi binari separati per ciascun gruppo.

Non sono sicuro di come viene eseguito il clustering (è possibile creare cluster multipli che soddisfano la condizione delta che si cita.) Perché hai scelto questo particolare cluster?). Si può anche considerare di avere un gigantesco albero di ricerca binaria per memorizzare tutti i valori e designare alcuni dei nodi come "teste di cluster" (cioè gli elementi nel sottoalbero che contiene questo nodo è un cluster). In questo modo, dovresti essere in grado di creare ed eliminare nuovi cluster.

Answer 2

Credo che sia possibile farlo utilizzando un albero di ricerca binario bilanciato di alberi di diffusione per garantire il tempo ammortizzato O (log n) per ogni operazione.

Supponiamo che non stessimo facendo alcun raggruppamento. In tal caso, è possibile archiviare tutti gli elementi in un albero di ricerca binario bilanciato per ottenere l'inserimento O (log n), la cancellazione e find-min. Ma con il clustering, questo cambia. Il mio suggerimento è di mantenere un BST dei cluster ordinati per l'intervallo di valori contenuto nel cluster, in cui ogni cluster è rappresentato come un albero di diffusione dei nodi in esso contenuti.

Per inserire un elemento nella struttura dati, eseguire una ricerca nel BST per il predecessore e il successore dell'elemento in questione. Se il nodo non appartiene a nessuno di questi cluster, crea un albero di diffusione singleton da quel nodo e inseriscilo nel BST.Se è contenuto esattamente in uno dei due cluster che hai trovato, inseriscilo in quel cluster. Se è contenuto in entrambi i cluster, rimuovere entrambi i cluster dal BST, unirli in un unico cluster, inserire il nuovo nodo in quel cluster, quindi reinserire il cluster nel BST. Il tempo di ricerca in tutti i casi in O (log n) per trovare i due cluster, quindi O (log n) tempo ammortizzato da inserire in un cluster. L'unione di due alberi splay è veramente veloce qui; poiché i cluster non sono stati uniti prima, un albero contiene valori tutti rigorosamente maggiori di tutti i valori nell'altro albero, quindi l'unione può essere eseguita in O (log n) tempo ammortizzato rimuovendo i puntatori. Anche il costo di rimuovere i due alberi e di aggiungerli è O (log n).

Per trovare il valore minimo del cluster massimo, trovare il cluster massimo nel BST in O (log n) ora, quindi trovare l'elemento minimo del cluster che si trova nel tempo O (log n) ammortizzato.

Per eliminare un elemento, trovare il cluster che lo contiene in tempo O (log n). Se si trova nel proprio cluster, eliminare il cluster Fromm l'albero. In caso contrario, rimuovere l'elemento dal cluster in cui si trova, quindi trovare il suo predecessore e il successore all'interno di quel cluster. Se sono all'interno del delta l'uno dell'altro, allora il cluster è ancora valido e abbiamo finito. Altrimenti, il cluster deve essere diviso. Nel tempo ammortizzato O (log n), dividere il cluster nel cluster di nodi inferiore o uguale al predecessore e maggiore o uguale al successore, quindi reinserire entrambi i cluster nell'albero.

Nel complesso, questo fornisce O (log n) ammortizzato per ciascuna operazione.

Spero che questo aiuti!