Lab 7 Implement a MaxHeap class to contain Integers

Lab 7
Implement a MaxHeap class to contain Integers

a. Implement a class MaxHeap (a max heap) that contains integers that represent both the priority and name of
the object.
 Implement class MaxHeap of integers:
o def __init__(self, capacity=50) Constructor creating an empty heap with default capacity = 50
but allows heaps of other capacities to be created.
o def insert (self, item) . // inserts “item” into the heap, returns true if successful, false if there is
no room in the heap
o def find_max(self) returns max without changing the heap and return None if not found
o def del_max(self) returns max and removes it from the heap and restores the heap property and
return None if heap is empty
o def heap_contents (self) returns a list of contents of the heap in the order it is stored internal to
the heap. (This may be useful for in testing your implementation.)
o def build_heap (self, alist) Method buildHeap that has a single explicit argument “list of int”
and builds a heap using the bottom up method discussed in class. It should return True if the
build was successful and False if the capacity of the MaxHeap object is not large enough to hold
the “array of int” argument.
o def is_empty(self) returns True if the heap is empty, false otherwise
o def is_full(self) returns True if the heap is full, false otherwise
o def get_heap_cap(self) --- this is the maximum number of a entries the heap can hold - 1 less
than the number of entries that the array allocated to hold the heap can hold.
o def get_heap_size(self) -- the actual number of elements in the heap, not the capacity
 Where possible your build, insert, and delete methods should use the following functions that work
exactly as described in class.
o def perc_down(self, i) where the parameter i is an index in the heap and perc_down moves the
element stored at that location to its proper place in the heap rearranging elements as it goes.
Since this is an internal method we will assume that the element is either in the correct position
or the correct position is below the current position.
o def perc_up(self, i):. similar specification as perc_down, see class notes
Normally these would be private but make them public for testing purposes.
b. Add a function heap_sort_increase (alist) to perform heap sort given a list of positive integers.
Add a function to the MaxHeap Class to sort a list of positive integers in increasing order.
 heap_sort_increase (alist) takes a list of integers and returns a list containing the integers in nondecreasing order using the Heap Sort algorithm as described in class. Since your MaxHeap class is a
max heap using the list internal to the heap to store the sorted elements will result in them being sorted
in increasing order. This enables the reuse of the space but will destroy the heap order property.
However, then you can just return the appropriate part of the internal list since you will not be using the
heap anymore.
Submissions:
1) heap_lab.py containing the above and a file
2) heap_file_tests.py containing your set of test cases.
Your test cases should test all the functions. Some are quite simple to test but some will require multiple
test cases. Again, developing test cases as you develop each function will save you time overall.