如何设计插入无限数组

Question

问题陈述

想象一下,我们有一个无限数组,我们存储整数.当n元素在数组中时,仅使用n第一个单元格,其余为空.

我正在尝试提出一种数据结构/算法,它能够:

• 检查元素是否存储
• 插入新元素(如果尚未存储)
• 删除元素(如果已存储)

每个操作都必须在O(sqrt(n)).

方法1

我遇到过这个网站,其中提出了以下算法:

• 该阵列(实际上,想象一下)分为子阵列.它们的长度分别为1,4,9,16,25,36,49等.最后一个子阵列不是一个完美的正方形 - 它可能无法完全填充.
• 假设当我们将这些子阵列视为集合时 - 它们的顺序递增.因此,右侧更远的堆的所有元素都比左侧堆中的任何元素大.
• 每个这样的子阵列代表二进制堆.最大堆.
• 查找:转到堆的第一个索引(所以再次是1,4,9,16 ......),只要你发现第一个堆的最大值(最大值存储在那些索引上)大于你的数量.然后检查这个子数组/堆.
• 插入:执行查找后,将元素插入堆应该在的位置.堆已满 - 获取最大元素并将其插入下一个堆.等等.

不幸的是,这个解决方案O(sqrt(n) * log(n)).

如何让它变得纯净O(sqrt(n))？

想法2

由于所有操作都需要执行查找,因此我认为插入和删除都是O(1).只是一个猜测.并且可能一旦插入完成,删除将是显而易见的.

澄清

什么是无限阵列是什么意思？

基本上,您可以在其中存储任意数量的元素.这是无限的.但是,有两个限制.首先 - 一个单元格只能存储一个元素.第二 - 当数组当前存储n个元素时,只能使用n个第一个单元格.

订单怎么样？

不要紧.

Answer 1

您是否考虑过双亲堆（又名：BEAP）？

堆保持高度为sqrt(n)，这意味着插入、查找和删除都在O(sqrt(n))最坏的情况下运行。

Munro 和 Suwanda 1980 年的论文《用于快速搜索和更新的隐式数据结构》中描述了这些结构。