wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> guessing what data structure could fit 
        
(Message started by: transgalactic on Jan 18^th, 2012, 11:44am)

Title: guessing what data structure could fit
Post by transgalactic on Jan 18^th, 2012, 11:44am

propose a data structure S which its operations
follows the following time complexity
n-is the number of member
BUILD(s) -builds the data structure S in O(n)
MIN(s)-return the minimal value of S in O(1)
DEL-MEDIAN(s) - deletes the median of S in O(lgn)
OS-MED7(S) - return the (n/2+7) order statistics of S in O(1)

the DEL-MEDIAN time of lgn sugests that it has
caracteristics of black-red tree

MIN and OS-MED time complexities suggests that its part of hash table.

what structure is it?