First we know min-heap is a data structure which supports the following
operators in O (lg n) complexity (n is the number of elements in the heap):
1. insert (H, x): the operator insert key x into a heap H in O (lg n)
2. extract_min (H): the operator delete and return the minimum key value
in the heap H, runs in O (lg n).
3. min (H): return the minimum key value in the heap H. Runs in O (1)
max-heap is similar data structure which supports extract_max instead
of extract_min and max instead of min.
Now, back to the original problem. We need to handle a data structure
named "Black Box"(by the problem's description) which has a member variable
i initially to be zero. The Black Box provides two operators:
1. Add (B, x): insert a key x in the black box B
2. Get (B): increase i by 1 and return the i-th smallest number in black-box B
We can implement Black Box by maintaining a RB-tree (this is also the
original solution which discussed this afternoon), but here I'll post an
easier implement way by using two heaps:
We maintain two heaps. One is max-heap and one is min-heap. And make sure
the max-heap has precisely (i - 1) elements (recall i is the member
variable to the Black Box), and the rest elements all in the min-heap.
Also we need to make sure all elements in the max-heap is equal or less than
the elements in the min-heap.
Now, we'll implement the Black Box's two operators in O (lg n):
1. Add (B, x):
if x is less than min (min-heap) then
insert (max-heap, x)
insert (min-heap, extract_max (max-heap))
else
insert (min-heap, x)
2. Get (B):
insert (max-heap, extract_min (min-heap))
return max (max-heap)
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.198