How to find the top n products based on number items sold. We can use max heap to keep track of number of times product was sold and find the top n from the heap. But the problem is let's say we have to find in real time when a product is brought we have to update the count and then heapify. Finding the product in heap is again O(N), deleting the product and adding back the product with updated count is O(LogN) Is there any better solution?
1 Answers
There is rather simple data structure based on binary heap - indexed (indirect) binary heap. You have some objects in an array, their indices are in heap, this heap is ordered by some object property/complex key. So you can easily update object keys, keeping heap in order. Seeking is not needed.
This structure is described, for example, in the book Algorithms of Robert Sedgewick and Kevin Wayne.
Very simple end concise implementation is available online
Note that retrieving of top n products takes nlogN time. If you have to know top n at every step, consider also approach with two heaps - like hour glass - lower one is max-heap, upper one is min-heap. When upper heap top (really bottom) becomes smaller than top of lower heap, exchange these items.
(Alike aproach is sometimes used in algorithms of online median determination, so you may also look at corresponding questions)
Related