Use Python Programming to modify and improve the heap sort code by:

Heap Sort Code:

from binheap import BinHeap # methods: BinHeap(), insert(item), delMin(), isEmpty(), size()

def heapSort(myList): minHeap = BinHeap()

# Add all list items to minHeap for item in myList: minHeap.insert(item) # delMin heap items back to list in sorted order for index in range(len(myList)): myList[index] = minHeap.delMin()

BinHeap Code just for reference:

class BinHeap: def __init__(self): self.heapList = [0] self.currentSize = 0

def buildHeap(self,alist): i = len(alist) // 2 self.currentSize = len(alist) self.heapList = [0] + alist[:] # print(len(self.heapList), i) while (i > 0): # print(self.heapList, i) self.percDown(i) i = i - 1 # print(self.heapList,i) def percDown(self,i): while (i * 2) self.heapList[mc]: tmp = self.heapList[i] self.heapList[i] = self.heapList[mc] self.heapList[mc] = tmp i = mc def minChild(self,i): if i * 2 + 1 > self.currentSize: return i * 2 else: if self.heapList[i * 2]

def percUp(self,i): while i // 2 > 0: if self.heapList[i]

def delMin(self): retval = self.heapList[1] self.heapList[1] = self.heapList[self.currentSize] self.currentSize = self.currentSize - 1 self.heapList.pop() self.percDown(1) return retval def isEmpty(self): if self.currentSize == 0: return True else: return False

def size(self): return self.currentSize

def __str__(self): return str(self.heapList[1:])

class FooThing: def __init__(self,x,y): self.key = x self.val = y

def getKey(self): return self.key

def getValue(self): return self.val

def setValue(self, newValue): self.val = newValue

def __lt__(self,other): if self.key

def __gt__(self,other): if self.key > other.key: return True else: return False def __hash__(self): return self.key

For Part B, I want you to modify and improve heap sort (still sorting in ascending order) by: * eliminating the usage of the BinHeap class by using the list parameter (e.g., myList) to store items rearranged as a heap and "in-line" the code for heap methods right into the heap-sort code, so your heap-sort code calls no methods improve the building of the initial "max-heap" containing all of the list items (called heapifying the list) by: use index 0 to hold the root of the max-heap. This changes the relationship of parent and child indexes. A node at index i has: a left child at i*2+1, a right child at i*2+2, and a parent at (i-1)//2 use the concept employed in the "buildHeap" method in the BinHeap class: (1) think of the leaves as mini max-heaps of size 1 and (2) percolate down the non-leaves starting at index (len(myList)//2 - 1) through index 0 into the smaller heaps below to form bigger-and-bigger heaps. while percolating down the non-leaves, don't repeatedly "swap" down a branch of the heap (e.g., 3 moves per swap), but instead "insert" the non-leaf item into the correct spot in the branch by shifting larger children up the branch (one move per shift) before inserting at the correct spot use the max-heap of all list items in the unsorted part to perform a selection-sort like sort. After heapifying the list in the above step we have: Unsorted Part as a max-heap Empty Sorted Part 0 23 45 myList: | 60 | 50 | 25 | 40 | 45 | 20 | 10 | 35 | 15 "swap" max. item in heap at index 0 with lastUnsortedIndex to grow sorted part of the list Unsorted Part as a max-heap Sorted Part Los L50L25T401 451201101 35160 myList percolate 15 down to restore heap-order across unsorted part Unsorted Part as a max-heap Sorted Part myList: | 50 | 45 | 25 | 40 | 1,5 | 20 | 10 | 35 | 60 shift 50 shift 45 insert 15 For Part B, I want you to modify and improve heap sort (still sorting in ascending order) by: * eliminating the usage of the BinHeap class by using the list parameter (e.g., myList) to store items rearranged as a heap and "in-line" the code for heap methods right into the heap-sort code, so your heap-sort code calls no methods improve the building of the initial "max-heap" containing all of the list items (called heapifying the list) by: use index 0 to hold the root of the max-heap. This changes the relationship of parent and child indexes. A node at index i has: a left child at i*2+1, a right child at i*2+2, and a parent at (i-1)//2 use the concept employed in the "buildHeap" method in the BinHeap class: (1) think of the leaves as mini max-heaps of size 1 and (2) percolate down the non-leaves starting at index (len(myList)//2 - 1) through index 0 into the smaller heaps below to form bigger-and-bigger heaps. while percolating down the non-leaves, don't repeatedly "swap" down a branch of the heap (e.g., 3 moves per swap), but instead "insert" the non-leaf item into the correct spot in the branch by shifting larger children up the branch (one move per shift) before inserting at the correct spot use the max-heap of all list items in the unsorted part to perform a selection-sort like sort. After heapifying the list in the above step we have: Unsorted Part as a max-heap Empty Sorted Part 0 23 45 myList: | 60 | 50 | 25 | 40 | 45 | 20 | 10 | 35 | 15 "swap" max. item in heap at index 0 with lastUnsortedIndex to grow sorted part of the list Unsorted Part as a max-heap Sorted Part Los L50L25T401 451201101 35160 myList percolate 15 down to restore heap-order across unsorted part Unsorted Part as a max-heap Sorted Part myList: | 50 | 45 | 25 | 40 | 1,5 | 20 | 10 | 35 | 60 shift 50 shift 45 insert 15