Tengo una colección de elementos (big racionales) que voy a procesar. En cada caso, el procesamiento consistirá en eliminar el elemento más pequeño de la colección, hacer algún trabajo y luego agregar de 0 a 2 elementos nuevos (que siempre será más grande que el elemento eliminado). La colección se inicializará con un elemento y el trabajo continuará hasta que esté vacío. No estoy seguro de qué tamaño alcanzará la colección, pero esperaría en el rango de 1M a 100M elementos. No necesitaré ubicar ningún artículo que no sea el más pequeño.¿Es un árbol rojo-negro mi estructura de datos ideal?
Actualmente estoy planeando utilizar un árbol rojo-negro, posiblemente ajustado para mantener un puntero al elemento más pequeño. Sin embargo, nunca he usado uno antes, y no estoy seguro si mi patrón de uso se adapta bien a sus características.
1) ¿Existe algún peligro de que el patrón de eliminación desde la izquierda + inserción aleatoria afecte el rendimiento, por ejemplo, requiriendo un número de rotaciones significativamente mayor que la eliminación aleatoria? ¿O las operaciones de eliminación e inserción seguirán siendo O (log n) con este patrón de uso?
2) ¿Alguna otra estructura de datos me daría un mejor rendimiento, ya sea por el patrón de eliminación o aprovechando el hecho de que solo tengo que encontrar el artículo más pequeño?
Actualización: me alegro de haber preguntado, el montón binario es claramente una mejor solución para este caso, y como prometió resultó ser muy fácil de implementar.
Hugo
A menos que sepa con certeza que los nodos que se deben eliminar lógicamente no serán necesarios para los valores recién calculados, es posible que desee ignorar o retrasar las eliminaciones. Un enfoque Halt & Sweep debería funcionar para este último, donde las raíces de los subárboles que se han vuelto demasiado desordenadas son visitadas por el código de reequilibrio para reequilibrar en'masse. Esto evita la degeneración bruta, a la vez que ofrece la perspectiva probable de un rendimiento sin eliminación. – RocketRoy