1

哪个更好，实现堆栈以获取最小元素或维护堆数据结构以提取最小元素。两者都给出了 O(1) 中的最小元素（如果您实现 2 个堆栈，一个具有最小元素，另一个堆栈具有实际输入）。

解释一下，在哪些情况下我们可以使用堆栈或堆来提取最小或最大元素以及为什么

4

4 回答 4

2

您基本上可以使用基于两个堆栈的解决方案来找到最小值，但它不是有效的（因为它消耗 2*N 内存而堆消耗 N 内存）并且堆栈应该用于其他目的。

于 2013-03-15T18:06:40.343 回答
2

类似堆栈的数据结构[1] 和堆都支持“获取最小值”操作。（请注意，我们谈论的是堆数据结构，而不是用于内存分配的“堆”。）它们都允许添加新元素。

它们在删除元素方面有所不同。具体来说，使用堆栈，您可以按照与插入相反的顺序删除元素。使用堆，您可以按值顺序删除元素（即始终删除最小值）。

所以你应该使用支持你需要的操作的那个。

[1] 所指的数据结构要么是两个并行的堆栈，要么是一对项目的堆栈；在这两种情况下，堆栈都会将添加的项目和最小值保持到该点，这可以在 中计算O(1)，因为它只是推送的项目的最小值和之前的最小值。

于 2013-03-15T18:15:56.820 回答
0

MinHeaps 旨在快速为您提供最小元素。只需查看最小元素（不删除）就需要 O(1)（恒定）时间。通常，您将删除最小元素，这将迫使您重新堆化堆，这需要 log(n) 时间。维基百科文章绘图显示了 MaxHeap，但实现 MinHeap 几乎相同。

要在（单个）堆栈中找到最小元素需要n时间（并且 log(n) < n），因为您必须搜索堆栈中的所有元素才能找到最小值。因此，您需要pop()关闭每个元素，检查它是否小于您记住的最小值，然后将其 push() 到辅助堆栈上，直到您遍历整个堆栈。因此，如果获取最小元素是数据结构的主要目的，您通常会希望使用 MinHeap。

另一方面，其他人提到的双栈解决方案的操作（add、remove、getMin）复杂度为 O(1)，而 removeMin 的时间复杂度为 O(n)。在最坏的情况下，它还需要 2N 空间。

总结一下：

              add/push 1    remove/pop 1   peekMin   removeMin   space
              ==========    ============   =======   =========   =====
one stack         O(1)          O(1)         O(n)       O(n)       n
two stacks        O(1)          O(1)         O(1)       O(n)      2n
minHeap         O(log(n)        N/A          O(1)     O(log n)     n

正如@rici 指出的那样，minHeap 支持 O(log n) 中的 removeMin 操作，即比堆栈快，但是，对于 add/remove 和 peekMin，两堆栈解决方案更快。minHeap 也不维护“大于”和“小于”关系之外的顺序。

于 2013-03-15T18:19:38.660 回答
0

我真的不明白这个问题。

似乎类似于问题：我应该使用锤子还是水壶？答案是：目的是什么？

堆和栈的目的/行为是不同的。

Heap 提供 API，例如：Insert(Key x)、GetandDeleteMin()

虽然堆栈提供了一个 LIFO（后进先出）API：Push(Value x)、Value Pop()（如果需要，还有 GetMin()）。

你应该问自己的问题是，我需要一个支持 min 的 LIFO 结构吗？如果是这样，您可以使用堆栈。

或者

我是否需要一个“优先级结构”，我可以在其中以随机顺序插入，并删除具有最高/最低优先级的结构？如果是这样，您可以使用堆。

即您应该首先查看您需要的行为。

所有这些比较运行时间和空间使用情况的答案对我来说似乎也很奇怪。当用法本质上不同时，进行这种比较有什么意义呢？首先确定行为，然后如果您有选择，请进行时间/空间等比较。

你真正在寻找什么？

于 2013-03-16T06:52:55.953 回答