CODEWITHSUNDEEP
algorithmdata-structuresstack
zangw
zangw

Reputation: 48476

Special stack to find medium

From this, we can design data structure special stack with method getMin() which should return minimum element from the SpecialStack.

My question is: How to implement the method getMed() which should return the medium element from the SpecailStack?

From this Data Structure to find median, we know the best data structure is two heaps. Left is a Max-Heap; Right is a Min-Heap. However, for my question it seems not good, because the top element pushed into stack must be maintained which heap can not do that. Am I right?

Edit I do not know how to maintain the index of latest pushed element with Heap.

Thanks a lot.

Upvotes: 0

Views: 189

Answers (2)

John Kurlak
John Kurlak

Reputation: 6680

You could alternatively use an Order Statistic Tree.

Upvotes: 2

kraskevich
kraskevich

Reputation: 18566

You can use any balanced binary search tree here instead of a heap. It is easy to find min or max element in a tree(the leftmost and the rightmost node), and it also supports deletion in O(log N).

So you can maintain a stack and two binary search trees(instead of two heaps). Push implementation is pretty strainforward. To pop an element, you can delete the top element from a tree where it is stored, adjust the trees(like in two heaps algorithm) and then pop it from the stack.

Upvotes: 0

Related Questions