import heapq

$\text{'}\text{'}\text{'}$

You are working for a promising new music streaming service $$Algo$-$fy$.$

Algo$-$fy would like to offer a new ranking feature that will track the top k most streamed songs of the day.

You$$ve been tasked with building a class $$AlgoFy$$ that can track the most streamed songs

and return an accurate list top k list at any point in time.

Another team has already developed the song streaming feature: iStream and you will need to integrate with it$.$

iStream will send AlgoFy play data as it processes customer requests.

This data will be batched so the AlgoFy class will need to ingest lists of played songs multiple times

A song is identified with an integer id number.

The AlgoFy class will need to have the following methods:

$-$ Constructor$($k$)$: the number of songs to track in the topk

$-$ streamSongs$($List of songIds$)$: Receive a batch of streamed songs $=>$ updates internal state

$-$ getTopK$()$: return the top k most streamed songs in order

As an example, the AlgoFy class may see the following usage:

ranker $=$ new AlgoFy$(2)$

ranker.streamSongs$([1,1,2,2,3])$

ranker.streamSongs$([3,3,3,1,2,1,3])$

ranker.getTopK$()=>[3,1]$

ranker.streamSongs$([2,2,2,2,2])$

ranker.getTopK$()=>[2,3]$

You must solve this problem by effectively using the properties of a Priority Queue or Heap.

You must also provide an explanation of the running time of both getTopK and streamSongs

Code Author:

Running Time Analysis of get$\_$top$\_$k

$--------------------$

Running Time Analysis of stream$\_$songs

$--------------------$

$\text{'}\text{'}\text{'}$

class AlgoFy:

def $\_\_$init$\_\_($self$,$ k$)$:

self.k $=$ k

def stream$\_$songs$($self$,$ songIds$)$:

pass

def get$\_$top$\_$k$($self$)$:

return $[]$

$"""$

DO NOT EDIT BELOW THIS

Below is the unit testing suite for this file.

It provides all the tests that your code must pass to get full credit.

$"""$

class TestAlgoFy:

def run$\_$unit$\_$tests$($self$)$:

self.test$\_$example$()$

self.test$\_$example$\_2()$

self.test$\_$many$\_$batches$()$

self.test$\_$fewer$\_$than$\_$k$()$

self.test$\_$empty$()$

$"""$

The test below will slow down your code if the runtime is inefficient.

Save this test for last. Once you have somewhat finalized code, uncomment this

test case and see if your code still runs quickly.

If it runs too slowly, there's a chance the autograder on Gradescope will

time out and not be able to grade your code within the allotted time.

$"""$

self.test$\_$very$\_$large$\_$k$()$

def print$\_$test$\_$result$($self$,$ test$\_$name, result$)$:

color $="\backslash 033[92$m$"$ if result else $"\backslash 033[91$m$"$

reset $="\backslash 033[0$m$"$

print$($f$"\{$color$\}[\{$result$\}]\{$test$\_$name$\}\{$reset$\}")$

def test$\_$answer$($self$,$ test$\_$name, result, expected$)$:

if result $==$ expected:

self.print$\_$test$\_$result$($test$\_$name, True$)$

else:

self.print$\_$test$\_$result$($test$\_$name, False$)$

print$($f$"$Expected: $\{$expected$\}$

Got: $\{$result$\}")$

def test$\_$example$($self$)$:

ranker $=$ AlgoFy$(2)$

ranker.stream$\_$songs$([1,1,2,2,3])$

ranker.stream$\_$songs$([3,3,3,1,2,1,3])$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=[3,1]$

self.test$\_$answer$("$test$\_$example", result, expected$\_$answer$)$

def test$\_$example$\_2($self$)$:

ranker $=$ AlgoFy$(2)$

ranker.stream$\_$songs$([1,1,2,2,3])$

ranker.stream$\_$songs$([3,3,3,1,2,1,3])$

ranker.get$\_$top$\_$k$()$

ranker.stream$\_$songs$([2,2,2,2,2])$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=[2,3]$

self.test$\_$answer$("$test$\_$example$\_2",$ result, expected$\_$answer$)$

def test$\_$many$\_$batches$($self$)$:

ranker $=$ AlgoFy$(5)$

for i in range$(1,10)$:

for j in range$(1,15)$:

ranker.stream$\_$songs$([$i$,$ j$])$

ranker.get$\_$top$\_$k$()$

ranker.stream$\_$songs$([3,1,1,1,2,3])$

ranker.stream$\_$songs$([5,4,4,3,2,2,2,1,1])$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=[1,2,3,4,5]$

self.test$\_$answer$("$test$\_$many$\_$batches", result, expected$\_$answer$)$

def test$\_$fewer$\_$than$\_$k$($self$)$:

ranker $=$ AlgoFy$(4)$

ranker.stream$\_$songs$([1,2,3,1,2,3,1,2,1])$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=[1,2,3]$

self.test$\_$answer$("$test$\_$fewer$\_$than$\_$k$",$ result, expected$\_$answer$)$

def test$\_$empty$($self$)$:

ranker $=$ AlgoFy$(3)$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=[]$

self.test$\_$answer$("$test$\_$empty", result, expected$\_$answer$)$

def test$\_$very$\_$large$\_$k$($self$)$:

ranker $=$ AlgoFy$(1000)$

for i in range$(1001)$:

for j in range$(100)$:

for z in range$($i$+1)$:

ranker.stream$\_$songs$([$i$])$

result $=$ ranker.get$\_$top$\_$k$()$

expected$\_$answer $=$ list$($range$(1000,0,-1))$

self.test$\_$answer$("$test$\_$very$\_$large$\_$k$",$ result, expected$\_$answer$)$

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

test$\_$runner $=$ TestAlgoFy$()$

test$\_$runner.run$\_$unit$\_$tests$()$