Top 10 players minheap sort - need help

[radhar4]

I am doing minheap sort to find out the Top 10 players based upon their scores.

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.

 

[WhiteCube]

I am doing minheap sort to find out the Top 10 players based upon their scores.

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.

The routine named heapify is doing what's called percolate down.

Percolate up is similar, it checks a node with its parent, swaps if necessary, going upwards towards the root, stopping when no swap is needed.

If the program had a heap INSERT routine, and a heap REMOVE routine, then the sort is not needed.

The player's name will need to be stored with their score in a node.

What follows is pseudocode.

Let n be the current quantity of nodes in the heap.

to REMOVE the root:
array[0] assign array[n-1]
n assign n-1
percolate down from 0

to INSERT x:
n assign n+1
array[n-1] assign x
percolate up from n-1

main loop:
read x
if n < k then
  INSERT x
else
  if root score < x then
    REMOVE the root
    INSERT x
  end if
end if

finish:
REMOVE the root, until n=0