algorithm - 在 O(1) 中查找插入删除和 getMin 的数据设计问题

Question

如标题中所述，我需要定义一个数据结构，插入删除只需要 O(1) 时间，getMIn 时间....没有空间限制......

我已经搜索了 SO 相同的内容，我发现的是在 O(1) 时间内插入和删除....即使是堆栈也是如此。我在堆栈溢出中看到了之前的帖子，他们说的只是散列...

根据我在 O(1) 时间内对 getMIn 的分析，我们可以使用堆数据结构
对于 O(1) 时间的插入和删除，我们有堆栈...

所以为了实现我的目标，我认为我需要调整堆数据结构和堆栈...... 我将如何向这种情况添加散列技术......

如果我使用散列表，那么我的散列函数应该是什么样子，如何根据散列来分析情况...任何好的引用资料都将不胜感激...

Answer 1

如果您最初假设插入和删除是 O(1) 复杂度(如果您只想插入顶部并从顶部删除/弹出，那么堆栈工作正常)那么为了让 getMin 返回您需要以某种方式存储最小值的恒定时间内的最小值。如果你只有一个成员变量来跟踪最小值，那么如果它被从堆栈中删除会发生什么？您将需要下一个最小值，或者相​​对于堆栈中剩余的最小值。为此，您可以让堆栈中的元素包含它认为是最小值的元素。堆栈在代码中由链表表示，因此链表中节点的结构如下所示:

struct Node
{
  int value;
  int min;
  Node *next;
}

如果您查看示例列表:7->3->1->5->2。让我们看看这将如何构建。首先将值 2 压入(到空堆栈)，这是最小值，因为它是第一个数字，跟踪它并在构造它时将其添加到节点:{2, 2}。然后你将 5 压入堆栈，5>2 所以最小值是相同的压入 {5,2}，现在你有 {5,2}->{2,2}。然后你插入 1，1<2 所以新的最小值是 1，推 {1, 1}，现在是 {1,1}->{5,2}->{2,2} 等等。到最后你有:

{7,1}->{3,1}->{1,1}->{5,2}->{2,2}

在此实现中，如果您弹出 7、3 和 1，您的新最小值将是 2，因为它应该是。并且您的所有操作仍处于恒定时间，因为您只是向节点添加了比较和另一个值。 (你可以使用 C++ 的 peek() 之类的东西，或者只使用指向列表头部的指针来查看堆栈的顶部并在那里获取最小值，它会在恒定时间内为你提供堆栈的最小值).

此实现中的一个权衡是您的节点中会有一个额外的整数，如果您在一个非常大的列表中只有一两分钟，那就是浪费内存。如果是这种情况，那么您可以在单独的堆栈中跟踪分钟数，只需将要删除的节点的值与该列表的顶部进行比较，如果匹配则将其从两个列表中删除。要跟踪的事情更多，所以这实际上取决于具体情况。

免责声明:这是我在这个论坛上的第一篇文章，所以如果它有点令人费解或冗长，我很抱歉。我也不是说这是“一个真正的答案”，而是我认为最简单且符合问题要求的答案。总是需要权衡取舍，并且根据不同的情况需要不同的方法。