I am doing minheap sort to find out the Top 10 players based upon their scores.
Output is:
Player16
Player21
Player24
Player11
Player18
Player22
Player15
Player12
Player17
Player13
I want to rewrite the code to make some improvements as below,
" Use only read first k lines where k refers to the top results that you have to return. Construct a minHeap out of it.
Then, read one line in every iteration. For that line, check if you should insert it in minheap"
I am not sure how to do this extensible. Need help or guidance on this please.
Python:
player score file:
Player11 1000
Player12 300
Player13 200
Player14 150
Player15 400
Player16 3500
Player17 250
Player18 1000
Player19 101
Player21 2000
Player22 900
Player23 90
Player24 1004
Player25 100
Player26 90
Code:
def min_heapify(arr,n,i):
smallest = i
left = (2*i)+1
right = (2*i)+2
if left < n and arr[smallest] > arr[left]:
smallest = left
if right < n and arr[smallest] > arr[right]:
smallest = right
if smallest != i:
arr[smallest],arr[i] = arr[i],arr[smallest]
min_heapify(arr,n,smallest)
def heapsort(scores):
for i in range(n-1,0,-1):
scores[0],scores[i] = scores[i],scores[0]
min_heapify(scores,i,0)
# Driver
players = []
scores = []
player_score = {}
with open("player_scores.txt", "r") as f:
for line in f.readlines():
player, score = line.split(" ")
score = int(score.rstrip())
players.append(player)
scores.append(score)
player_score[player] = score
# build max heap
n = len(scores)
for i in range(n//2 -1, -1, -1):
min_heapify(scores,n,i)
heapsort(scores)
print(scores[0:10])
for i in range(10):
for player,score in player_score.items():
if scores[i] == score and scores[i] != scores[i-1]:
print(player)
Output is:
Player16
Player21
Player24
Player11
Player18
Player22
Player15
Player12
Player17
Player13
I want to rewrite the code to make some improvements as below,
" Use only read first k lines where k refers to the top results that you have to return. Construct a minHeap out of it.
Then, read one line in every iteration. For that line, check if you should insert it in minheap"
I am not sure how to do this extensible. Need help or guidance on this please.