Estructura de datos para elegir elementos aleatorios?

Question

¿Alguien sabe de una estructura de datos que admita las dos operaciones de manera eficiente?

1. Inserta un valor en la estructura de datos.
2. Dequeue y devuelve una entrada de la estructura de datos con probabilidad aleatoria uniforme.

Esto es algo así como la canónica "bolsa de canicas" que siempre aparece en las clases introductorias de probabilidad. Puedes poner mármoles arbitrarios en la bolsa y luego puedes eliminar los mármoles al azar.

La mejor solución que tengo es la siguiente: utilice un árbol de búsqueda binaria autoequilibrante (AVL, AA, rojo/negro, etc.) para almacenar los elementos. Esto da O (lg n) tiempo de inserción. Para eliminar un elemento aleatorio, elija un índice aleatorio i, luego ubique y elimine el i-ésimo elemento del árbol. Si ha aumentado la estructura de forma adecuada, también se puede ejecutar en tiempo O (lg n).

Este tiempo de ejecución ciertamente no es malo, pero tengo curiosidad si es posible hacerlo mejor, quizás O (1) para inserción y O (lg n) para dequeues? O tal vez algo que se ejecuta en espera O (1) inserte y elimine usando funciones hash? ¿O tal vez un límite amortizado más fuerte?

¿Alguien tiene alguna idea sobre cómo hacer esto de manera asintótica más rápido?

Answer 1

Sí. Usa un vector

Para insertarlo, simplemente colóquelo en el extremo e incremente el tamaño. Para eliminarlo, elija un elemento al azar, intercambie su contenido con el valor final y, a continuación, extraiga el valor final (es decir, devuelva el valor final y disminuya el tamaño del vector).

Ambas operaciones se amortizan O (1).