哪一个更好，实现一个堆栈来获得最小的元素，还是维护一个堆数据结构来提取最小的元素。两者都给出了O(1)中的最小元素(如果你实现了2个堆栈，一个具有最小元素，另一个具有实际输入)。
请解释一下，在哪些情况下我们可以使用Stack或heap来提取最小或最大元素，为什么
类堆栈的数据结构[1]和堆都支持"get minimum"操作。(注意，我们讨论的是堆数据结构，而不是用于内存分配的"堆"。)它们都允许添加新元素。
它们的不同之处在于删除元素。具体来说，对于堆栈，您可以按照插入的相反顺序删除元素。使用堆，你可以按值顺序删除元素(即总是删除最小值)。
所以你应该使用支持你所需要的操作的那个。
[1]所指的数据结构要么是两个并行堆栈，要么是一堆成对的数据项;在这两种情况下，堆栈都保留了添加的项和到该点的最小值，这可以在O(1)中计算，因为它只是推入的项和前一个最小值的最小值。
您基本上可以使用基于两个堆栈的解决方案来找到最小值，但它并不有效(因为它消耗2*N内存，而堆消耗N内存)，并且堆栈应该用于其他目的。
minheap旨在非常快速地为您提供最小元素。仅仅查看最小元素(不移除)需要O(1)(常数)时间。通常，您将删除最小元素，这将迫使您重新堆积堆，这需要log(n)时间。维基百科的文章图显示了MaxHeap，但实现MinHeap几乎是相同的。
查找(单个)Stack中的最小元素需要n time(和log(n) <n)，因为你必须搜索堆栈中的所有元素才能找到最小值。因此，您需要将每个元素取消pop()，检查它是否小于您记住的最小值，并将它压入辅助堆栈，直到您遍历整个堆栈。因此，如果获取最小元素是数据结构的主要目的，则通常需要使用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操作，即比堆栈更快，然而，对于添加/移除和peekMin，两堆栈解决方案更快。除了"大于"one_answers"小于"的关系之外，minHeap也不维护顺序。
我不太明白这个问题。
似乎类似于这个问题:我应该用锤子还是罐子?答案是:为了什么目的?
Heap和Stack的目的/行为不同。
Heap提供如下API: Insert(Key x)， GetandDeleteMin()
而堆栈提供了后进先出(后进先出)API: Push(Value x)， Value Pop()(如果你想，GetMin())。
你应该问自己的问题是，我需要一个支持min的后进先出结构吗?如果是这样，可以使用堆栈。
或
我是否需要一个"优先级结构"，我可以在其中插入随机顺序，并删除具有最高/最低优先级的?如果是这样，可以使用堆。
。你应该首先看看你需要的行为。
所有这些比较运行时间和空间使用的答案对我来说也很奇怪。当用法本质上不同时，做这种比较有什么意义呢?首先确定行为，然后如果你有选择的话，做时间/空间等的比较。
你真正想要的是什么?