mngharbi's blog

By mngharbi, 4 weeks ago, In English,

Suppose we have a group of items with a unique key. We can either view an item, or get the top k viewed items.

Obviously, for retrieval O(k) is the best we can do.

My idea is to maintain a min-heap containing the top k elements (key, views) and a hash table mapping a key to an element in the heap, and another one mapping keys to views.

When viewing an item: if it's in the heap, it will still be in the heap but we have to bubble it down. If it's not in the heap, add it to the heap if size of the heap < k. Or if the views have surpassed the minimum, we take out the top and insert the new value.

This would guarantee O(k) retrieval (but not sorted, we can sort them in O(klogk) though), and O(log k) updates.

Is there a better way?