1

Which one is better, Implementing a stack to get minimum element or maintaing a heap data structure to extract minimum element. Both gives minimum element in O(1) (If you implement 2 stack, one with minimum element and another stack with actual input).

Explain me, under which situations we can use Stack or heap to extract minimum or maximum element and why

rajkumarts
  • 399
  • 1
  • 7
  • 20
  • Did you really mean Stack? Maybe Tree? – Roman Mar 15 '13 at 17:56
  • @Roman - ya Stack. This is frequently asked in interviews and the interviewer asked to implement using a stack. – rajkumarts Mar 15 '13 at 18:00
  • Are you asking about the *system* stack and *system* heap for memory allocation, or are you referring to using stack and heap data structures? – mbeckish Mar 15 '13 at 18:17
  • @mbeckish - Heap and Stack Data Structure .. I am sorry for the confusion.. I changed my Question now . – rajkumarts Mar 15 '13 at 18:21
  • You can augment the stack to give you minimum, maximum, geometric/arithmetic mean, etc. in O(1). Just store those values along with the actual values and update on each push(). – G. Bach Mar 15 '13 at 21:17

4 Answers4

3

Both a stack-like datastructure[1] and a heap support the "get minimum" operation. (Note that we're talking about the heap datastructure, not the "heap" which is used for memory allocation.) Both of them also allow the addition of a new element.

They differ in the removal of an element. Specifically, with a stack, you can remove elements in the reverse order to their insertion. With a heap, you can remove elements in order by value (i.e. always remove the minimum).

So you should use the one which supports the operation you need.

[1] The datastructure referred to is either two parallel stacks, or a stack of pairs of items; in both cases, the stack keeps both the item added and the minimum value up to that point, which can be computed in O(1), since it is simply the minimum of the item pushed and the previous minimum.

rici
  • 234,347
  • 28
  • 237
  • 341
  • How does a stack support an O(1) "get minimum" operation? Are you referring to the two stack solution that Roman linked to? – mbeckish Mar 15 '13 at 18:19
  • @mbeckish - yes by maintaing 2 stacks you can support O(1) "get minimum" operation – rajkumarts Mar 15 '13 at 18:20
  • @mbeckish, yes, I should have made that clearer. – rici Mar 15 '13 at 18:25
  • @rici: if the heap is maintained as a tree can we not remove the minimum in O(1) ? I agree there is wasted space due to tree pointers. – user1952500 Mar 15 '13 at 18:27
  • @user1952500: in a heap, we can remove the minimum, generally in `O(log n)`. But it's difficult to remove "the last element pushed". That's what I said: "remove elements in order" – rici Mar 15 '13 at 18:30
  • +1: For "So you should use the one which supports the operation you need". – Knoothe Mar 16 '13 at 06:59
2

You basically can use a solution based on two stacks to find the minimum value, but it's not effective (because it consumes 2*N memory while a heap consumes N memory) and stacks are supposed to be used for other purposes.

Community
  • 1
  • 1
Roman
  • 64,384
  • 92
  • 238
  • 332
  • ok that makes sense considering the space stack consumes. Even if we remove the minimum element from the stack the ordering of heap is going to take O(nlogn) which I guess is better than maintaing 2 stacks – rajkumarts Mar 15 '13 at 18:15
0

MinHeaps are designed to give you the minimum element very quickly. Just peeking at the minimum element (without removing) takes O(1) (constant) time. Usually, you will remove the minimum element, which will force you to re-heapify the heap, which takes log(n) time. The wikipedia article drawing shows a MaxHeap, but implementing a MinHeap is almost identical.

To find the minimum element in a (single) Stack takes n time (and log(n) < n), since you'll have to search all the elements in the Stack to find the minimum. So you'll need to pop() each element off, check if it is smaller than the minimum you remembered, and push() it onto an auxiliary stack until you went through the entire stack. Therefore, you will generally want to use a MinHeap if getting the minimum element is the main purpose of your data structure.

On the other hand, the two-stack solution referred to by others has O(1) complexity for operations (add, remove, and getMin), but O(n) time for removeMin. It also has 2N space requirements in the worst case.

To summarize:

              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

As @rici points out minHeap, supports removeMin operation in O(log n) i.e, faster than the stacks, however, for add/remove and peekMin, two-stack solution is faster. minHeap also does not maintain order, outside of relations "greater than" and "less than".

angelatlarge
  • 4,086
  • 2
  • 19
  • 36
  • The "two-stack" datastructure's remove-min operation is O(n). pop() is not the same as remove-min. – rici Mar 15 '13 at 23:35
  • Yes, you are right. I should be more careful and break down the operations by data structure by running time. Thanks! – angelatlarge Mar 15 '13 at 23:39
0

I don't really understand the question.

Seems similar to the question: Should I use a hammer or a jug? The answer for that is: for what purpose?

The purpose/behavior of a Heap and Stack are different.

Heap provides API like: Insert(Key x), GetandDeleteMin()

While stack provides a LIFO (last in first out) API: Push(Value x), Value Pop() (and if you want, GetMin()).

The question you should be asking yourself is, do I need a LIFO structure which supports min? If so, you can use a stack.

OR

Do I need a "priority structure" where I can insert in random order, and remove the one with the highest/lowest priority? If so, you can use a heap.

i.e. you should be looking at the behavior you need first.

All these answers comparing run time and space usage seem strange to me too. What is even the point of doing that comparison when the usage is essentially different? First determine the behavior, and then if you have a choice, do the time/space etc compares.

What is it that you are really looking for?

Knoothe
  • 1,218
  • 8
  • 14
  • my question is where and when to use them and i think you made a point by finding whats the behavior and then chose the data structure .. thanks – rajkumarts Mar 17 '13 at 21:02