Có ai biết cấu trúc dữ liệu hỗ trợ hai thao tác một cách hiệu quả không?Cấu trúc dữ liệu để chọn các phần tử ngẫu nhiên?
- Chèn giá trị vào cấu trúc dữ liệu.
- Hủy bỏ và trả lại mục nhập từ cấu trúc dữ liệu với xác suất ngẫu nhiên thống nhất.
Đây giống như "túi bi" kinh điển luôn xuất hiện trong các lớp xác suất giới thiệu. Bạn có thể đặt các viên bi tùy ý vào trong túi, và sau đó có thể loại bỏ các viên bi một cách hiệu quả một cách ngẫu nhiên.
Giải pháp tốt nhất tôi có được như sau - sử dụng cây tìm kiếm nhị phân tự cân bằng (AVL, AA, đỏ/đen, v.v.) để lưu trữ các phần tử. Điều này cho thời gian chèn O (lg n). Để loại bỏ một phần tử ngẫu nhiên, chọn một chỉ số ngẫu nhiên i, sau đó tìm và loại bỏ phần tử thứ i từ cây. Nếu bạn đã tăng cường cấu trúc một cách thích hợp, điều này có thể được thực hiện để chạy trong thời gian O (lg n).
Thời gian chạy này chắc chắn không phải là xấu, nhưng tôi tò mò nếu nó có thể làm tốt hơn - có lẽ O (1) để chèn và O (lg n) cho dequeues? Hoặc có lẽ một cái gì đó chạy trong mong đợi O (1) chèn và xóa bằng cách sử dụng hàm băm? Hoặc có lẽ một ràng buộc amortized mạnh hơn?
Có ai có ý tưởng nào về cách thực hiện điều này nhanh hơn không?
Chỉ vì tò mò: có ai biết liệu cấu trúc dữ liệu này có tên không? Đó rõ ràng là một loại 'Bag' và/hoặc' MultiSet'. 'RandomBag', có thể? Trong thực tế, cấu trúc dữ liệu như thế nào (tức là cấu trúc dữ liệu trong đó 'pop' trả về và loại bỏ một phần tử ngẫu nhiên) được gọi là * nói chung *? –
Tôi đã nghe các điều khoản Bag và RandomBag được sử dụng ở đây, nhưng tôi nghĩ RandomBag có lẽ là thuật ngữ thích hợp; Túi thường là một từ đồng nghĩa với multiset. – templatetypedef