3

I want to know that when we can sort a stack with a Collections.sort method so why we need a new data structure like max heap?thanks

user355002
  • 871
  • 2
  • 10
  • 22
  • I doesn't make much sense to sort a stack. Can you give an example of why you would do this? I haven't heard of a "max heap" data structure, could you add a link to its javadoc? – Peter Lawrey Jun 13 '10 at 08:17
  • we have heap data structure that has two kinds of itself (Min heap and max heap) – user355002 Jun 13 '10 at 08:27
  • @Peter heap = priority queue, that's the name used in Collections. Agree, "sorted stack" makes no sense. – Sean Owen Jun 13 '10 at 08:49
  • 2
    @matin1234: you have gone to the direction where I did NOT want you to go. There is no such thing as a sorted stack. The fact that you can `Collections.sort` a `java.util.Stack` betrays the stack specification. http://stackoverflow.com/questions/3028810/about-sorting-algorithms/ – polygenelubricants Jun 13 '10 at 09:34
  • @matin1234: I think it will help us make you understand if YOU now explain to us what you think a stack is. – polygenelubricants Jun 13 '10 at 10:01
  • @Sean Owen: Which Collections are you reffering to? I did a search of the javadoc for Collections and the word "heap" doesn't appear. I did a google for "heap collection" but this didn't help either. – Peter Lawrey Jun 15 '10 at 19:36

3 Answers3

6

Stack and heap have totally different properties and usages.

Stack is needed for LIFO. Sorting it will cost O(N*logN), Push/pop O(1).

Heap is needed for priority queue for example, getting the min/max element will cost O(1), inserting an element O(log(N))

You need to determine the usage pattern and goals and then decide what exactly you need.

Drakosha
  • 11,925
  • 4
  • 39
  • 52
1

Collections.sort takes O(n log n). So while it would be correct to simulate a heap with a list by invoking Collections.sort after every operation, it would be needlessly inefficient. A heap allows you to insert any element or retrieve the top element in O(log n).

Collections.sort is fine when you have to sort once. When you have to keep a collection sorted while its is being modfied, using a sorted data structure (such as a heap, or a tree) is more efficient.

meriton
  • 68,356
  • 14
  • 108
  • 175
0

It depends on your requirement. Access pattern in Stack and Heap is completely different. Stack is implemented as simple list while Heap is implemented as priority queue. Sorting time in stack is O(nlog(n)) while you can extract element of maximum priority(Max/Min) in O(log(n)) time.

So your question where to use MaxHeap, think of a scenario where you have to find 7th largest element out of 1000. In stack have to sort first and then 7th from start(descending sorted) will be solution but using MaxHeap you have to extract element 7 times and 7th one will be the solution. So it depends on your scenario that which one can be better for you.

GG.
  • 2,835
  • 5
  • 27
  • 34