class MinHeap:

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

self.H $=[$None$]$

def size$($self$)$:

return len$($self$.$H$)-1$

def $\_\_$repr$\_\_($self$)$:

return str$($self$.$H$[1$:$])$

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

for i in range$(2,$ len$($self$.$H$))$:

assert self.H$[$i$]>=$ self.H$[$i$//2],$ f'Min heap property fails at position $\{$i$//2\},$ parent elt: $\{$self$.$H$[$i$//2]\},$ child elt: $\{$self$.$H$[$i$]\}\text{'}$

def min$\_$element$($self$)$:

return self.H$[1]$

## bubble$\_$up function at index

## WARNING: this function has been cut and paste for the next problem as well

def bubble$\_$up$($self$,$ index$)$:

assert index $>=1$

if index $==1$:

return

parent$\_$index $=$ index $//2$

if self.H$[$parent$\_$index$]<$ self.H$[$index$]$:

return

else:

self.H$[$parent$\_$index$],$ self.H$[$index$]=$ self.H$[$index$],$ self.H$[$parent$\_$index$]$

self.bubble$\_$up$($parent$\_$index$)$

## bubble$\_$down function at index

## WARNING: this function has been cut and paste for the next problem as well

def bubble$\_$down$($self$,$ index$)$:

assert index $>=1$ and index $<$ len$($self$.$H$)$

lchild$\_$index $=2*$ index

rchild$\_$index $=2*$ index $+1$

# set up the value of left child to the element at that index if valid, or else make it $+$Infinity

lchild$\_$value $=$ self.H$[$lchild$\_$index$]$ if lchild$\_$index $<$ len$($self$.$H$)$ else float$(\text{'}$inf$\text{'})$

# set up the value of right child to the element at that index if valid, or else make it $+$Infinity

rchild$\_$value $=$ self.H$[$rchild$\_$index$]$ if rchild$\_$index $<$ len$($self$.$H$)$ else float$(\text{'}$inf$\text{'})$

# If the value at the index is lessthan or equal to the minimum of two children, then nothing else to do

if self.H$[$index$]<=$ min$($lchild$\_$value, rchild$\_$value$)$:

return

# Otherwise, find the index and value of the smaller of the two children.

# A useful python trick is to compare

min$\_$child$\_$value, min$\_$child$\_$index $=$ min $(($lchild$\_$value, lchild$\_$index$),($rchild$\_$value, rchild$\_$index$))$

# Swap the current index with the least of its two children

self.H$[$index$],$ self.H$[$min$\_$child$\_$index$]=$ self.H$[$min$\_$child$\_$index$],$ self.H$[$index$]$

# Bubble down on the minimum child index

self.bubble$\_$down$($min$\_$child$\_$index$)$

# Function: heap$\_$insert

# Insert elt into heap

# Use bubble$\_$up$/$bubble$\_$down function

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

# your code here

self.H$.$append$($elt$)$

self.bubble$\_$up$($len$($self$.$H$)-1)$

# Function: heap$\_$delete$\_$min

# delete the smallest element in the heap. Use bubble$\_$up$/$bubble$\_$down

def delete$\_$min$($self$)$:

# your code here

if len$($self$.$H$)==1$:

return None

# Save the minimum value to return it later

min$\_$val $=$ self.H$[1]$

# Replace the root with the last element in the heap

self.H$[1]=$ self.H$[-1]$

# Remove the last element

self.H$.$pop$()$

# Restore the heap property by bubbling down the root element

self.bubble$\_$down$(1)$

return min$\_$val