Resource hog

Problem: Resource hog

During this winter break I was trying to improve my networking background. So I've spend some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices by George Varghese'. Thanks Vlad Balan for trecommending the book, it's fun to see how networking interacts heavily with the algorithms world. I read a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG
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 author the problem asks for a datastructure 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.

To paraphrase, the problem asks for a data structure with the following operations
 
* use_resources(name, quantity) which does resources[name] += quantity (quantity can also be negative)
* get_approximate_max() which returns name1 such that max(resources[name]) / 2 <=  resources[name1] <= max(resources[name])
 
Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?

private

protected

10640