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

5
  • Did you really mean Stack? Maybe Tree?
    – Roman
    Mar 15, 2013 at 17:56
  • @Roman - ya Stack. This is frequently asked in interviews and the interviewer asked to implement using a stack.
    – rajkumarts
    Mar 15, 2013 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, 2013 at 18:17
  • @mbeckish - Heap and Stack Data Structure .. I am sorry for the confusion.. I changed my Question now .
    – rajkumarts
    Mar 15, 2013 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, 2013 at 21:17

4 Answers 4

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.

6
  • 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, 2013 at 18:19
  • @mbeckish - yes by maintaing 2 stacks you can support O(1) "get minimum" operation
    – rajkumarts
    Mar 15, 2013 at 18:20
  • @mbeckish, yes, I should have made that clearer.
    – rici
    Mar 15, 2013 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. Mar 15, 2013 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, 2013 at 18:30
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.

1
  • 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, 2013 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".

2
  • The "two-stack" datastructure's remove-min operation is O(n). pop() is not the same as remove-min.
    – rici
    Mar 15, 2013 at 23:35
  • Yes, you are right. I should be more careful and break down the operations by data structure by running time. Thanks! Mar 15, 2013 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?

1
  • 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, 2013 at 21:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.