有没有办法在O(1)中找到max并在O(lgN)中进行查找？

Question

假设您有许多(键,值)对象要跟踪,包括许多插入和删除.

您需要满足3个要求:

1. 在任何时刻获得恒定时间内的最大键
2. 在对数时间内查找任何键的值.
3. 插入和删除采用对数时间.

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

我的想法:

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

Answer 1

为什么我们需要那些奇特的数据结构？我认为跟踪Max节点的简单二进制搜索树可以很好地满足OP的要求.

1. 您可以使用max key跟踪节点:

   无论何时插入新节点,都要将密钥与先前的最大密钥进行比较,以确定这是否是新的最大节点

   无论何时删除最大节点,都需要O(logN)来查找下一个最大节点

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

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

Answer 2

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

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

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

希望这可以帮助！