A software or hardware module needs to keep track of resources required by various users. The module needs a cheap way to find the user consuming the most resources. Since ordinary heaps are too slow, the device designers are willing to relax the system requirements to be off by a factor of 2. Can this relaxation in accuracy requirements be translated into a more efficient algorithm?

To paraphrase, the problem asks for a data structure with the following operations:

To paraphrase, the problem asks for a data structure with the following operations
 

* use_resources(name, quantity) which does resources[name] += quantity
* get_approximate_top() which returns name1 such that max(resources[name]) / 2 <=  resources[name1] <= max(resources[name])

Using a map in combination with a hash table gets a solution that has O(log n) complexity for use_resources and get_approximate
_top which is too slow.