哪种数据结构可以比O(n)时间更好地实现随机弹出和推送? [英] What data structure can achieve random pop and push in better than O(n) time?

问题描述

我正在尝试设计一种支持随机弹出和插入操作的数据结构.根据其重量随机弹出一个元素.例如，如果数据结构具有元素"a"，则为"a".和"b"表示重量为"10"的和"20"表示然后是元素"b"弹出的可能性是"a"的两倍. n 是元素的数量.权重可以是浮点数或整数，并且是> = 0 .

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.

我认为分段树或二进制索引树可能能够在O(log n)时间内完成两项操作，但我不确定.任何人有更好的主意吗?

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?

推荐答案

一种不同类型的顺序统计树应该能够做到:拥有一个自平衡二进制搜索树，其中每个节点还存储其子树的总权重(标准版本将存储其基数).

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).

插入和删除已经在O(log n)时间完成，也可以在O(log n)时间进行加权随机采样:首先从0到整个树的总权重，并从根节点开始.假设 t 是随机数， l 是左子树的总权重(如果没有，则为零)，而 c 是当前节点的权重:

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:

• 如果 t<l ，然后在左侧子树上递归.
• 否则，如果 t-l<c ，然后在当前节点中返回该项目.
• 否则，从 t 中减去 l + c 并递归到右子树上.

• 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.

这篇关于哪种数据结构可以比O(n)时间更好地实现随机弹出和推送?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！