Структура данных для выбора случайных элементов?
Кто-нибудь знает о структуре данных, которая эффективно поддерживает две операции?
- Вставляет значение в структуру данных.
- Удаляет из очереди и возвращает вход из структуры данных с равномерно случайной вероятностью.
Это что-то вроде канонического «мешка с шариками», который всегда встречается во вводных классах вероятности. Вы можете положить в сумку произвольные шарики, а затем эффективно удалить шарики наугад.
Лучшее решение, которое у меня есть, следующее - использовать самобалансирующееся двоичное дерево поиска (AVL, AA, красный / черный и т. Д.) ) для хранения элементов. Это дает время вставки O (lg n). Чтобы удалить случайный элемент, выберите случайный индекс i, затем найдите и удалите i-й элемент из дерева. Если вы соответствующим образом увеличили структуру, это также может быть выполнено за время O (lg n).
Эта среда выполнения определенно неплоха, но мне любопытно, можно ли сделать лучше - возможно, O (1) для вставки и O (lg п) для раздачи? Или, возможно, что-то, что выполняется в , ожидалось O (1) вставки и удаления с использованием хэш-функций? Или, может быть, более сильная амортизированная граница?
Есть ли у кого-нибудь идеи, как сделать это асимптотически быстрее?