algorithm - Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations -
i came across question: implement queue in push_rear(), pop_front() , get_min() constant time operations.
i thought of using min-heap data structure has o(1) complexity get_min(). push_rear() , pop_front() o(log(n)).
does know best way implement such queue has o(1) push(), pop() , min()?
i googled this, , wanted point out algorithm geeks thread. seems none of solutions follow constant time rule 3 methods: push(), pop() , min().
thanks suggestions.
you can implement stack o(1) pop(), push() , get_min(): store current minimum each element. so, example, stack [4,2,5,1]
(1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]
.
then can use 2 stacks implement queue. push 1 stack, pop one; if second stack empty during pop, move elements first stack second one.
e.g pop
request, moving elements first stack [(4,4), (2,2), (5,2), (1,1)]
, second stack [(1,1), (5,1), (2,1), (4,1)]
. , return top element second stack.
to find minimum element of queue, @ smallest 2 elements of individual min-stacks, take minimum of 2 values. (of course, there's logic here case 1 of stacks empty, that's not hard work around).
it have o(1) get_min()
, push()
, amortized o(1) pop()
.
Comments
Post a Comment