from HeapInt import * \'\'\'* * An implementation of a minimum heap with handles
ID: 3846268 • Letter: F
Question
from HeapInt import *
'''*
* An implementation of a minimum heap with handles
'''
class Heap:
def __init__(self):
'''
The constructor has been set up with an initial array of size 4
so that your doubleHeap() method will be tested. Don't change
this!
'''
self.array = [0]*4
self.heapsize = 0
self.arraysize = 4
def exchange(self, pos1, pos2):
'''
Exchanges that values at positions pos1 and pos2 in the heap array.
Handles must be exchanged correctly as well.
Running time = O(????)
'''
# Provide your implementation here
def doubleHeap(self):
'''
Doubles the size of the array. A new array is created, the elements in
the heap are copied to the new array, and the array data member is set
to the new array. Data member arraysize is set to the size of the
new array.
Running time = O(????)
'''
# Provide your implementation here
def heapifyDown(self, pos):
'''
Fixes the heap if the value at position pos may be bigger than one of
its children. Using exchange() to swap elements will simplify your
implementation. HeapElts contain records, and records contain
keys; you will need to decide how to handle comparisons.
Running time = O(????)
'''
# Provide your implementation here
def heapifyUp(self, pos):
"""
Fixes the heap if the value at position pos may be smaller than its
parent. Using exchange() to swap elements will simplify your
implementation. HeapElts contain records, and records contain
keys; you will need to decide how to handle comparisons.
Running time = O(????)
"""
# Provide your implementation here
def insert(self, inElt):
'''
Insert inElt into the heap. Before doing so, make sure that there is
an open spot in the array for doing so. If you need more space, call
doubleHeap() before doing the insertion.
Running time = O(????) (NOTE that there are a couple of different cases
here!)
'''
# Provide your implementation here
def removeMin(self):
'''
Remove the minimum element from the heap and return it. Restore
the heap to heap order. Assumes heap is not empty, and will
cause an exception if the heap is empty.
Running time = O(????)
'''
# Provide your implementation here
def getHeapsize(self):
'''
Return the number of elements in the heap..
Running time = O(????)
'''
# Provide your implementation here
def printHeap(self):
'''
Print out the heap for debugging purposes. It is recommended to
print both the key from the record and the handle.
Running time = O(????)
'''
# Provide your implementation here