In this assignment you are to write a Python program to implement heapsort algorithm & apply it on a provided list.

You are provided with the template in which you must:

$(1)$ implement Phase II of a heapsort algorithm:

$(1\mathrm{.}1)$ function that sifts down the value of the heap root to a correct position, and

$(1\mathrm{.}2)$ function that finds the largest child of a given heap node.

Your program must:

take a file containing input list of values as a command line argument and print the original list,

create a heap form a given list of values and print created heap,

sort given list using heapsort algorithm $(1),$ and print sorted list.

Following is the output of the program run applied on a provided test file:

Together with your source code include a separate file

Namingformat.py with your information as the values of the

following variables:

myName $=$ 'first$\_$name last$\_$name'

myTechID $={?}^{\text{'}}{0000000}^{\text{'}}$

myTechEmail $=$ 'abc$123\text{'}$ #only your email id omit @latech.edu

You must properly cite the sources if you use any help from peers or any code$/$ideas from online resources. Failure to do

so will be treated as a plagiarism. Properly citing the sources should be done as a comment in your code. Some examples:

# found this code at:

# used idea from:

#

##### HAVE TO USE MY TEMPLATE #########

import sys

DEBUG $=$ False

class Heap:

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

self.size $=0$

self.capacity $=1$

self.data $=[$None$]$

def getData$($self$)$:

return self.data$[$:self.size$]$

def getSize$($self$)$:

return self.size

def isEmpty$($self$)$:

return self.size $==0$

def $\_\_$siftUp$($self$,$ child$)$:

parent $=($child $-1)//2$

while $($child $>0)$ and $($self$.$data$[$child$]>$ self.data$[$parent$])$:

temp $=$ self.data$[$child$]$

self.data$[$child$]=$ self.data$[$parent$]$

self.data$[$parent$]=$ temp

if DEBUG:

print$($f$"\{$self$.$data$[$parent$]\}$ swapped with $\{$self$.$data$[$child$]\}")$

child $=$ parent

parent $=($child $-1)//2$

def buildFrom$($self$,$ seq$)$:

self.data $=[$None$]*$len$($seq$)$

self.size $=$ self.capacity $=$ len$($seq$)$

for x in range$($self$.$size$)$:

self.data$[$x$]=$ seq$[$x$]$

index $=(2*$ self.data.index$($seq$[0]))+1$

while $($index $$ len$($seq$))$:

self.$\_\_$siftUp$($index$)$

index $+=1$

def addToHeap$($self$,$ newVal$)$:

if $($self$.$size $==$ self.capacity$)$:

self.capacity $*=2$

temp $=[$None$]*$ self.capacity

for i in range$($self$.$size$)$:

temp$[$i$]=$ self.data$[$i$]$

self.data $=$ temp

self.data$[$self$.$size$]=$ newVal

self.$\_\_$siftUp$($self$.$size$)$

self.size $+=1$

return newVal

def $\_\_$largestChild$($self$,$ index, lastIndex$)$:

$\text{'}\text{'}\text{'}$ Inputs:

$-$ index $->$ index of the current node

$-$ lastIndex $->$ index of the last node in the heap

Output:

$-$ index of the largest child if it exists, None otherwise

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

# find indexes of left and right child of the current $($index$)$ node

# return None if left child index is past last index

# otherwise return the index of the largest child

### WRITE YOUR CODE HERE###

def $\_\_$siftDownFromTo$($self$,$ fromIndex, last$)$:

$\text{'}\text{'}\text{'}$ Inputs:

$-$ fromIndex $->$ index of the node where to start sifting from

$-$ last $->$ index of the last node in the heap

Output:

$-$ the node sifted down as far as necessary to maintain heap conditions

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

# repeat until node is in the right position

# find index of a largest child

# if index of the largest child is not found then finish

# otherwise, if value of the largest child is larger than parent then swap

### WRITE YOUR CODE HERE###

def sort$($seq$)$:

h $=$ Heap$()$

h$.$buildFrom$($seq$)$

for i in range$($len$($seq$))$:

h$.$data$[0],$ h$.$data$[$h$.$size $-1]=$ h$.$data$[$h$.$size $-1],$ h$.$data$[0]$

h$.$size $-=1$

h$.\_\_$siftDownFromTo$(0,$ h$.$size $-1)$

return h$.$data

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

st $=$ f$"\backslash$tHeap size: $\{($self$.$size$)\}.$

$"$

st $+=$ f$"\backslash$tHeap capacity: $\{($self$.$capacity$)\}.$

$"$

st $+=$ f$"\backslash$tElements of heap:

$"$

for x in range$($self$.$size$)$:

st $+=$ f$"\backslash$t$\backslash$tValue: $\{($self$.$data$[$x$])\}$ at index: $\{$x$\}$

$"$

return st

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

return self.$\_\_$str$\_\_()$

def main$()$:

file $=$ open$($sys$.$argv$[1],"$r$")$

for line in file:

values $=[$int$($x$)$ for x in line.split$()]$

print$($f$"$Original list: $\{$values$\}$

$")$

### WRITE YOUR CODE HERE###

print$($f$"$Heapified list:

$\{$h$\}")$

sorted$\_$list $=$ Heap.sort$($values$)$

print$($