Answer:
A data structure suggestion for a set of n points given can be found in the following steps explanation.
Step-by-step explanation:
=>an array of two max-heaps (Xmax and Ymax) of type Point. An additional hashmap (with key as point and value as boolean) as a cache.
=> Point - an array of two integers/doubles
* Accessing any element in cache is O(1).
A. Insert : Insert point (x,y) into Xmax-heap which is sorted by x-coordinate and also insert (x,y) into Ymax which is sorted by y-coordinate.Set the cache of that element as valid(true).
Insertion is O(log(n)) + O(log(n)) + O(log(1)) = O(log(n)).
B. Extract Xmax : Extract the topmost element of the Xmax-heap, while checking that it is valid in cache.
This will take O(1). Set the cache of that element as invalid (false).
C. Extract Ymax : Extract the topmost element of the Ymax-heap, while checking that it is valid in cache.
This will take O(1). Set the cache of that element as invalid (false).
If you encounter the topmost element in any heap that is invalid in cache, delete it.
D. Initialization : Both the heaps can be initialized in O(n), using the concept of sifting. Also, the hashmap can be initialized in O(n). Hence, the total complexity of initialization is O(n).
