具有随机访问的快速,有序的数据结构？

Question

我想在一个允许这样的结构中添加几个对象:

1. 插入对象,立即对整个结构进行排序,这样我就有一个int的降序排列;

2. 能够更改对象排序的int(我的意思是:说对象编号为2,现在的int为5,所以它重新排序结构);

3. 结构快速,因为它将完全迭代60次;

4. 能够按位置直接访问对象;

5. 只需要从上到下迭代:更高的INT来降低INT

6. 不需要删除,但以后可能会有用.

关于如何使用该结构的一些迹象会很棒,因为我对C++标准库知之甚少.

Answer 1

您列出的所有操作(按索引查找除外)都可以由标准二进制搜索树支持,以整数值为键.这使您能够按排序顺序迭代元素,并在任何插入过程中保持对象的排序.正如@njr所提到的,您还可以通过从二叉搜索树中删除对象,更改其优先级,然后将它们重新插入二叉搜索树来更新优先级.

为了支持索引的随机访问,您应该考虑查看订单统计树,这是二进制搜索树上的一个变体,除了所有其他操作外,还支持通过索引快速(O(log n))查找元素.也就是说,您可以非常有效地查询排序序列中的第15个元素,或者第17个等.订单统计树不是C++标准库的一部分,但是这个较旧的问题包含可以将您链接到实现的答案.

希望这可以帮助!