14
Suppose that you have a large collection of key/value pairs, where the value is some arbitrary real number. You're interested in creating a data structure supporting the following operations:
- Insert, which adds a new key/value pair to the collection,
- Delete, which removes a key/value pair from the collection,
- Percentile, which tells which percentile the value associated with a given key is in, and
- Tell-Percentile, which accepts a percentile number and returns the key whose value is the lowest value at at least the given percentile.
This data structure could be used, for example, to efficiently determine what percentile a given student is in when receiving a stream of nationwide test scores, or to identify hospitals that have unusually good or bad quality of service.
Is there a way to make these operations run efficiently (say, sublinear time?)