2

假设您有很多（键、值）对象要跟踪，包括许多插入和删除。

你需要满足3个要求：

  1. 在任意点以恒定时间获取最大密钥
  2. 以对数时间查找任何键的值。
  3. 插入和删除需要对数时间。

有没有可以做到这一点的数据结构？

我的想法：

优先级队列可以在恒定时间内获得最大值，但我无法查找值。二叉搜索树（2-3棵树）可以在对数时间内查找，但max也需要O（lgN）。如果我尝试跟踪 BST 中的最大值，则当我必须删除最大值并找到第二大时需要 O(lgN)。

4

9 回答 9

10

为什么我们需要那些花哨的数据结构？我认为一个跟踪 Max 节点的简单二叉搜索树可以很好地满足 OP 的要求。

  1. 您可以使用 max 键跟踪节点：

    每当您插入一个新节点时，您都​​会将该键与前一个最大键进行比较以确定这是否是一个新的最大节点

    每当您删除最大节点时，都需要 O(logN) 才能找到下一个最大节点

  2. 你肯定有 O(logN) 查找时间与 BST 的性质

  3. BST 的更新需要 O(logN) 时间

于 2012-06-14T18:22:36.107 回答
4

您可以并行使用两个数据结构-

  1. 将键/值对存储在哈希表或平衡 BST 中以获得 O(log n) 查找，并且
  2. 将所有值存储在最大堆中，以便您可以在 O(1) 时间内查找最大值。

这使得插入或删除需要 O(log n) 时间，因为这是从最大堆中插入或删除的时间复杂度。

希望这可以帮助！

于 2012-06-14T17:45:12.390 回答
3

跳过列表有一个摊销O(logn)查找，它们是一个链表，min所以max总是O(1)。http://en.wikipedia.org/wiki/Skip_list

于 2012-06-14T17:53:25.270 回答
1

我知道哈希表的搜索时间为 O(1)，因为您使用键并且您可以立即查找该值。至于最大值，您可以在每次插入或删除值时不断跟踪它。

于 2012-06-14T17:45:34.497 回答
1

按降序排序的列表怎么样？

  1. 最大总是第一个，所以 O(1)。
  2. 通过二进制搜索查找是 O(log n)。
  3. n-i插入/删除是 O(n)，因为从位置 i 插入/删除时您必须移动项目。
于 2012-06-14T17:53:16.757 回答
1

由于您使用的是键值对，因此我建议您在 java 中使用 TreeMap 的最佳解决方案。

您可以简单地使用Treemap中的以下 4 种方法。

  • 用于插入和检索的 get() 和 put(key,value) 方法
  • lastKey() 用于查找最大键。
  • remove(key) 用于删除。

.或使用本页中的以下结构

定论：

如果您要权衡空间复杂性并热衷于运行时间，您需要有 2 个数据结构。

使用 O(1) 的 HashMap 或 TreeMap 进行插入、检索和删除。

然后根据我提供的第二个链接，使用双堆栈数据结构来查找 o(1) 的最大值或最小值。

我认为这是我能给出的最好的解决方案。

于 2012-06-15T07:29:58.437 回答
0

看一下RMQ（Range minimum-maximum Query）数据结构或者segment tree数据结构。它们都有 O(1) 查询时间，但是您必须以某种方式修改它们以存储值。

这是一篇不错的文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

于 2012-06-14T17:48:28.960 回答
0

正如第一条评论所说，使用max heap。使用hashmap将指针存储到堆中。这些用于恒定时间查找和日志时间删除。

堆的实现非常简单。它们不需要像 BST 那样的平衡。哈希图通常内置在您选择的语言中。

于 2012-06-14T21:30:08.697 回答
0

树数据结构中的删除已经是一个 O(logN) 操作，因此寻找第二大键不会改变操作的复杂性。

但是，您可以使元素无效而不是删除，并且如果您在数据结构中保留反向指针，则从最大移动到第二大可能是 O(N) 操作。

于 2012-06-15T08:22:05.313 回答