finding maximum value in a map

[hooshdar3]

Hi.
Suppose that a map is defined thus:
map<sttring, int> mymap;

I wanna find k maximum valuees.
Is there a way to find the maximum value in an efficient manner?
Or else, How can I sort them and then find the k first elements?

Thanks in advance

[abhishekm71]

You can follow this approach if k is very small with respect to N (the total number of elements):

1. Iterate through the map. Also, maintain a min-heap having k elements.
2. Insert the first k elements in the min-heap.
3. Now, (k+1)th element onwards, check the current element with the root element of the heap. If the current element is larger than the root, then pop out the root element and insert this current element in the heap.
4. Keep doing this for all elements in the map.

At the end of the procedure, your min-heap will have the k largest elements. Just pop out the root elements one after the other, they will come out in ascending order.

Time Complexity: O( N + klogk )
Space Complexity: O(k)