Структура данных для выбора случайных элементов?

Question

Кто-нибудь знает структуру данных, которая эффективно поддерживает две операции?

1. Вставить значение в структуру данных.
2. Вывести из очереди и вернуть запись из структуры данных с равномерно случайной вероятностью.

Это что-то вроде канонического «мешка мрамора», который всегда встречается во вводных классах вероятности. Вы можете положить в сумку произвольные шарики, а затем эффективно удалить шарики случайным образом.

Лучшее решение, которое у меня есть, заключается в следующем: использовать самобалансирующееся двоичное дерево поиска (AVL, AA, красный / черный и т. Д.) Для хранения элементов. Это дает O (LG N) время вставки. Чтобы удалить случайный элемент, выберите случайный индекс i, затем найдите и удалите i-й элемент из дерева. Если вы соответствующим образом увеличили структуру, это можно сделать так, чтобы она также выполнялась за O (lg n).

Эта среда выполнения, безусловно, неплохая, но мне любопытно, можно ли добиться большего успеха - возможно, O (1) для вставки и O (lg n) для изъятий? Или, может быть, что-то, что выполняется в Ожидается O (1) вставки и удаления с использованием хэш-функций? Или, может быть, более сильная амортизированная граница?

У кого-нибудь есть идеи, как сделать это асимптотически быстрее?

Answer 1

Да.Используйте вектор.

Чтобы вставить, просто поместите в конце и увеличьте размер.Чтобы удалить, выберите элемент случайным образом, поменяйте местами его содержимое с конечным значением, затем вытолкните из конечного значения (то есть верните конечное значение и уменьшите размер вектора).

Обе операции амортизируются O (1).