Top 10 players minheap sort - need help


Joined
Oct 3, 2022
Messages
1
Reaction score
0
I am doing minheap sort to find out the Top 10 players based upon their scores.

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.
 
Ad

Advertisements

Joined
Sep 21, 2022
Messages
17
Reaction score
2
I am doing minheap sort to find out the Top 10 players based upon their scores.

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.

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.

Code:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top