构建具有特定需求的数据结构

我需要构建一个仅使用O（n）位存储的数据结构。插入，删除和最大时间的最差时间需要为O（log n），但对于包含而言它需要为O（1）。我一直试图使用只有1和0的二进制堆（以满足存储的O（n）位），但我似乎无法获得最大值和包含函数（关于它们的最坏时间复杂度看起来如何）。任何人都可以给我一个关于我要去哪里的线索吗？谢谢。构建具有特定需求的数据结构

来源

2016-01-27 Daniel Cook

二元堆你不能实现'O（1）'查找时间 – user8

如何使用只有1和0的数组？ –

如果他们堆在一起，是的。令top为max（1），如果left为0（在A [1]处），则它包含1,0。类似于最小。一般来说，你只需要'A [0] == A [1]'来检查。但对我来说，仅仅分类1和0就没什么意义了。 – user8

有两个工作串联的数据结构：平衡BST（如AVL树）和哈希表。插入一个元素需要O（log（n））时间用于BST，O（1）时间用于散列表，所以O（log（n））时间的总和。删除需要O（log（n））时间BST，O（1）时间散列表。最大值为BST的O（log（n））时间，并且一旦知道哪个元素是最大值，则需要O（1）时间来计算哈希表。包含需要O（1）时间的散列表（之后，由于它们包含相同的元素，因此不需要检查BST）。实际上实现它会很困难，因为你需要在BST元素和哈希表中保留指针，但是这种结构可以达到所需的规范。

来源

2016-01-29 21:12:29 ghui

构建具有特定需求的数据结构

回答

相关问题