Alguém conhece uma estrutura de dados que suporta as duas operações com eficiência?

Inserir um valor na estrutura de dados.Retire da fila e retorne uma entrada da estrutura de dados com probabilidade uniformemente aleatória.

É como o "saco de bolas de gude" canônico que sempre aparece nas classes introdutórias de probabilidade. Você pode colocar bolas de gude arbitrárias na sacola e depois removê-las com eficiência de forma aleatória.

A melhor solução que tenho é a seguinte - use uma árvore de pesquisa binária com auto balanceamento (AVL, AA, vermelho / preto etc.) para armazenar os elementos. Isso fornece tempo de inserção de O (lg n). Para remover um elemento aleatório, escolha um índice aleatório i e localize e remova o i-ésimo elemento da árvore. Se você aumentou a estrutura adequadamente, isso também pode ser executado no tempo O (lg n).

Esse tempo de execução certamente não é ruim, mas estou curioso para saber se é possível fazer melhor - talvez O (1) para inserção e O (lg n) para desenfileiramentos? Ou talvez algo que funcioneesperado O (1) inserir e excluir usando funções de hash? Ou talvez um limite amortizado mais forte?

Alguém tem alguma idéia de como tornar isso assintoticamente mais rápido?