Struttura dati di mantenimento dei ranghi diversa da std :: vector?

Question

Sono di fronte a un'applicazione in cui devo progettare un contenitore che ha accesso casuale (o almeno migliore di O (n)) ha un inserto e una rimozione poco costosi (O (1)) e memorizza i dati secondo l'ordine (rank) specificato all'inserimento.

Per esempio se ho la seguente matrice:

[2, 9, 10, 3, 4, 6] 

posso chiamare l'rimuovere sull'indice 2 per rimuovere 10 e posso anche chiamare il inserto sull'indice 1 inserendo 13.

Dopo queste due operazioni avrei dovuto:

[2, 13, 9, 3, 4, 6] 

I numeri sono memorizzati in una sequenza e inserire/rimuovere operazioni richiedono un parametro di indice per specificare in cui inserire il numero o quale numero deve essere rimosso.

La mia domanda è, che tipo di strutture dati, oltre a un elenco collegato e un vettore, potrebbe mantenere qualcosa di simile? Mi sto appoggiando ad un Heap che dà la priorità al prossimo indice disponibile. Ma ho visto qualcosa su un albero di fusione utile (ma più in senso teorico).

Che tipo di strutture dati potrebbero darmi il miglior tempo di funzionamento pur mantenendo basso il consumo di memoria? Ho giocato con un ordine di inserimento preservando la tabella hash, ma finora non ha avuto successo.

---

La ragione per cui sto tirare fuori con uno std :: vector verso l'alto è perché devo costruire qualcosa che su preforme un vettore in termini di queste operazioni di base. La dimensione del contenitore ha la possibilità di crescere fino a centinaia di migliaia di elementi, quindi non è possibile effettuare il commit a turni in un vettore std ::. Lo stesso problema con una lista collegata (anche se doppiamente collegato), attraversandolo a un dato indice prenderebbe nel caso peggiore O (n/2), che è arrotondato a O (n).

Stavo pensando a un elenco di collegamenti raddoppiati che conteneva un puntatore Testa, Coda e Medio, ma ho ritenuto che non sarebbe stato molto meglio.

Answer 1

In un utilizzo di base, per poter inserire ed eliminare in una posizione arbitraria, è possibile utilizzare gli elenchi collegati. Consentono l'inserimento/la rimozione di O (1), ma solo a condizione di aver già localizzato la posizione nell'elenco in cui inserire. È possibile inserire "dopo un determinato elemento" (ovvero, dato un puntatore a un elemento), ma non è possibile inserire in modo efficiente "a un determinato indice".

Per poter inserire e rimuovere un elemento in base all'indice, è necessaria una struttura dati più avanzata. Esistono almeno due di queste strutture di cui sono a conoscenza.

Una è una struttura rope, disponibile in alcune estensioni C++ (SGI STL o in GCC tramite #include <ext/rope>). Permette l'inserimento/rimozione di O (log N) in posizione arbitraria.

Un'altra struttura consentendo di O (log N) inserire/rimuovere è una Treap implicita (implicita aka albero cartesiano), è possibile trovare alcune informazioni a http://codeforces.com/blog/entry/3767, Treap with implicit keys o https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.

Il treap implicito può anche essere modificato per consentire di trovare un valore minimo in esso (e anche per supportare molte più operazioni). Non sono sicuro che la corda sia in grado di gestirlo.

UPD: In realtà, credo che si può adattare qualsiasi O (log N) ricerca binaria albero (come AVL o albero rosso-nero) per la vostra richiesta per la conversione in schema "chiave implicito". Una struttura generale è la seguente.

Immaginate un albero di ricerca binaria che, in ciascun dato momento, memorizza i numeri 1, 2, ..., N come chiavi (N è il numero di nodi nell'albero). Ogni volta che cambiamo l'albero (inseriamo o rimuoviamo il nodo) ricalcoliamo tutte le chiavi memorizzate in modo che siano ancora da 1 al nuovo valore di N. Questo consentirà l'inserimento/rimozione in posizione arbitraria, poiché la chiave è ora la posizione , ma richiederà troppo tempo per l'aggiornamento di tutte le chiavi.

Per evitare questo, non archiviamo esplicitamente le chiavi nell'albero. Invece, per ogni nodo, memorizzeremo il numero di nodi nella sua sottostruttura. Di conseguenza, ogni volta che andiamo dalla radice dell'albero verso il basso, possiamo tenere traccia dell'indice (posizione) del nodo corrente - abbiamo solo bisogno di sommare le dimensioni dei sottoalberi che abbiamo alla nostra sinistra. Questo ci consente, dato k, di individuare il nodo che ha l'indice k (ovvero, che è il k-esimo nell'ordine standard dell'albero di ricerca binario), in O (log N) tempo. Dopodiché, possiamo eseguire l'inserimento o l'eliminazione in questa posizione utilizzando la normale procedura ad albero binario; avremo solo bisogno di aggiornare le dimensioni dei sottostrati di tutti i nodi modificati durante l'aggiornamento, ma questo è fatto facilmente in O (1) tempo per ogni nodo modificato, quindi il tempo totale di inserimento o di rimozione sarà O (log N) come in albero di ricerca binario originale.

Quindi questo approccio consente di inserire/rimuovere/accedere ai nodi in una determinata posizione in O (log N) tempo utilizzando qualsiasi albero di ricerca binaria O (log N) come base. Ovviamente è possibile memorizzare le informazioni aggiuntive ("valori") necessarie nei nodi, e si può anche essere in grado di calcolare il minimo di questi valori nell'albero semplicemente mantenendo il valore minimo della sottostruttura di ciascun nodo.

Tuttavia, la treccia e la corda di cui sopra sono più avanzate in quanto consentono anche operazioni di divisione e unione (prendendo una sottostringa/sottorazza e concatenando due stringhe/matrici).

Answer 2

Considera un elenco di salti, che può implementare operazioni di time rank lineare nella sua variazione "indexable".

Per gli algoritmi (pseudocodice), vedere A Skip List Cookbook, by Pugh.

È possibile che il metodo ad albero di ricerca binario "chiave implicita" delineato da @Petr sopra sia più facile da raggiungere e possa persino migliorare.