Coders Packet

Finding top k ratings in Python

By Akash Rawat

This packet consists of a Python program that gives k highest-rated elements among the elements available.

This program is in Python programming language and uses a min-Heap data structure. The basic concept is to go through the list of ratings once; and as we go through the list to keep a list of top k elements that we found so far. For this, we need to know the smallest rating in those top k ratings to possibly replace it with the coming rating that is greater than it. For this min-heap is very useful and efficient, we let the entries be pushed to min-heap till the size of the heap is less than k, as it reaches k, we compare the coming element with the root of min-heap which will also be the smallest rating in top k ratings found so far and then we pop the root and push the new entry into min-heap after which heapify process will take place. In this way with only one traversal of data and we will be able to find top k ratings.

Time complexity: O(nlogk) where n is the number of total ratings and k is the number of top ratings
Space complexity: O(k) where k is a number of top ratings we need to find.
command to run: "python3 topK.py"; Provide the value of k. then enter 1 to add new ratings or enter 2 to view the top 10 ratings and 3 to exit. (Usage video is included in the .zip file)

Where it can be used: It can be used in scenarios where we have to find top-k items, one such exemplar case is when we have to display top-rated items on a webpage.

 

Download Complete Code

Comments

No comments yet