class TopKHeap:

# The constructor of the class to initialize an empty data structure

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

self.k $=$ k

self.A $=[]$

self.H $=$ MinHeap$()$

def size$($self$)$:

return len$($self$.$A$)+($self$.$H$.$size$())$

def get$\_$jth$\_$element$($self$,$ j$)$:

assert $0<=$ j $<$ self.k$-1$

assert j $<$ self.size$()$

return self.A$[$j$]$

def satisfies$\_$assertions$($self$)$:

# is self.A sorted

for i in range$($len$($self$.$A$)-1)$:

assert self.A$[$i$]<=$ self.A$[$i$+1],$ f'Array A fails to be sorted at position $\{$i$\},\{$self$.$A$[$i$],$ self.A$[$i$+1]\}\text{'}$

# is self.H a heap $($check min$-$heap property$)$

self.H$.$satisfies$\_$assertions$()$

# is every element of self.A less than or equal to each element of self.H

for i in range$($len$($self$.$A$))$:

assert self.A$[$i$]<=$ self.H$.$min$\_$element$(),$ f'Array element A$[\{$i$\}]=\{$self$.$A$[$i$]\}$ is larger than min heap element $\{$self$.$H$.$min$\_$element$()\}\text{'}$

# Function : insert$\_$into$\_$A

# This is a helper function that inserts an element $`$elt$`$ into $`$self$.$A$`.$

# whenever size is $<$ k$,$

# append elt to the end of the array A

# Move the element that you just added at the very end of

# array A out into its proper place so that the array A is sorted.

# return the "displaced last element" jHat $($None if no element was displaced$)$

def insert$\_$into$\_$A$($self$,$ elt$)$:

print$("$k $=",$ self.k$)$

assert$($self$.$size$()<$ self.k$)$

self.A$.$append$($elt$)$

j $=$ len$($self$.$A$)-1$

while $($j $>=1$ and self.A$[$j$]<$ self.A$[$j$-1])$:

# Swap A$[$j$]$ and A$[$j$-1]$

$($self$.$A$[$j$],$ self.A$[$j$-1])=($self$.$A$[$j$-1],$ self.A$[$j$])$

j $=$ j $-1$

return

# Function: insert $--$ insert an element into the data structure.

# Code to handle when self.size $<$ self.k is already provided

def insert$($self$,$ elt$)$:

size $=$ self.size$()$

# If we have fewer than k elements, handle that in a special manner

if size $<=$ self.k:

self.insert$\_$into$\_$A$($elt$)$

return

# Code up your algorithm here.

# your code here

# Function: Delete top k $--$ delete an element from the array A

# In particular delete the j$^\{$th$\}$ element where j $=0$ means the least element.

# j must be in range $0$ to self.k$-1$

def delete$\_$top$\_$k$($self$,$ j$)$:

k $=$ self.k

assert self.size$()>$ k # we need not handle the case when size is less than or equal to k

assert j $>=0$

assert j $<$ self.k

# your code here