the difference between Max Heap and sorted stack

Question

Hi 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

Answer 1

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.

Answer 2

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.

Answer 3

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.