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