Cod*_*ggo 6 c++ heap rank data-structures insertion-order
我面临一个应用程序,我必须设计一个随机访问(或至少优于O(n))具有廉价(O(1))插入和删除的容器,并根据顺序存储数据(排名)插入时指定.
例如,如果我有以下数组:
[2, 9, 10, 3, 4, 6]
我可以调用索引2上的remove来删除10,我也可以通过插入13来调用索引1上的insert.
在我完成这两项操作之后:
[2, 13, 9, 3, 4, 6]
数字存储在一个序列中,插入/删除操作需要一个索引参数来指定应插入数字的位置或应删除的数字.
我的问题是,除了链接列表和向量之外,什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的Heap.但我一直在看一些关于融合树有用的东西(但在理论意义上更多).
什么样的数据结构可以在保持内存消耗的同时为我提供最佳的运行时间？我一直在玩一个保留哈希表的插入顺序,但到目前为止它还没有成功.
我直接使用std :: vector折腾的原因是因为我必须根据这些基本操作构造一些预先形成向量的东西.容器的大小有可能增长到数十万个元素,因此承诺在std :: vector中进行转换是不可能的.带有链接列表的相同问题行(即使是双重链接),将其遍历给定索引将采用最坏情况O(n/2),其舍入为O(n).
我想到了一个包含Head,Tail和Middle指针的双倍链表,但我觉得它不会好多了.
在基本用法中,为了能够在任意位置插入和删除,您可以使用链接列表.它们允许插入/移除O(1),但前提是您已经在列表中找到了要插入的位置.您可以插入"在给定元素之后"(即,给定指向元素的指针),但是您不能有效地插入"在给定索引处".
为了能够在给定索引的情况下插入和删除元素,您将需要更高级的数据结构.我知道至少存在两种这样的结构.
一种是绳索结构,可用于某些C++扩展(SGI STL或GCC via #include <ext/rope>).它允许在任意位置插入/移除O(log N).
允许为O(log N)插入/删除另一种结构是一个隐含的树堆(又名隐含笛卡尔树),你可以找到一些信息http://codeforces.com/blog/entry/3767,树堆与隐性键或HTTPS: //codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
也可以修改隐式treap以允许在其中找到最小值(并且还支持更多操作).不确定绳索是否可以处理这个问题.
UPD:事实上,我猜你可以通过将其转换为"隐式密钥"方案来为你的请求调整任何O(log N)二叉搜索树(例如AVL或红黑树).概述如下.
想象一下二叉搜索树,它在每个给定时刻存储连续数字1,2,...,N作为其键(N是树中节点的数量).每次我们更改树(插入或删除节点)时,我们重新计算所有存储的键,使它们仍然从1到N的新值.这将允许在任意位置插入/移除,因为键现在是位置,但是所有密钥更新都需要太多时间.
为避免这种情况,我们不会明确地在树中存储密钥.相反,对于每个节点,我们将在其子树中存储节点数.因此,无论何时我们从树根向下,我们都可以跟踪当前节点的索引(位置) - 我们只需要将左侧的子树大小相加.这允许我们在给定k的情况下,在O(log N)时间上定位具有索引k的节点(即,二进制搜索树的标准顺序中的第k个).在此之后,我们可以使用标准二叉树程序在该位置执行插入或删除; 我们只需更新更新期间更改的所有节点的子树大小,但这可以在每个节点更改的O(1)时间内轻松完成,因此总插入或删除时间将为O(log N),如原始的二叉搜索树.
因此,该方法允许使用任何O(log N)二分搜索树作为基础在O(log N)时间内在给定位置插入/移除/访问节点.您当然可以在节点中存储所需的附加信息("值"),甚至可以通过保持每个节点的子树的最小值来计算树中这些值的最小值.
然而,前面提到的treap和rope更高级,因为它们也允许分割和合并操作(采用子串/子阵列并连接两个字符串/数组).