CODEWITHSUNDEEP
algorithmdata-structures
user5965026
user5965026

Reputation: 485

What data structure can achieve random pop and push in better than O(n) time?

I'm trying to design a data structure that supports random pop and insert operations. An element is popped randomly in accordance with their weight. For example, if the data structure has elements "a" and "b" with weights "10" and "20" then element "b" will have twice the likelihood of being popped than "a." n is the number of elements. The weights can be floating point or integers and are >=0.

I am thinking that a segment tree or binary indexed tree may be able to achieve both operations in O(log n) time, but I'm not certain. Anyone have any better ideas?

Upvotes: 3

Views: 1641

Answers (1)

kaya3
kaya3

Reputation: 51152

A variant kind of order statistic tree should be able to do this: have a self-balancing binary search tree where each node also stores the total weight of its subtree (where a standard version would store its cardinality).

Insertion and removal are already done in O(log n) time, and it is possible to take a weighted random sample in O(log n) time too: start by generating a random number uniformly in the range from 0 to the total weight of the whole tree, and start at the root node. Let t be the random number, l be the total weight of the left subtree (or zero if there is none), and c be the weight of the current node:

  • If t < l then recurse on the left subtree.
  • Otherwise if t - l < c then return the item in the current node.
  • Otherwise subtract l + c from t and recurse on the right subtree.

Upvotes: 3

Related Questions