Lab 7 Solution

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.

(Note: Heap is like an array which start from index 1. Left child is in index i*2 and right child is in index i*2+1)

    • 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 heap is empty. 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) takes 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) returns the maximum number of a entries 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 (self, alist) to perform heap sort to a given list of positive integers. Add a function to the MaxHeap Class to sort a list of positive integers in increasing order.
        ◦ heap_sort_increase (self, alist) takes a list of integers and returns a list containing the integers in non-decreasing 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) max _heap.py containing the above and a file
    2) max_heap_tests.py containing your set of test cases.

Your test cases should test all the functions (two test cases for each function). Some are quite simple to test but some will require multiple test cases. Again, developing test cases as you develop each function. Believe me that will save you lost of time in overall. For every function have separate test case. Do not put all your test cases in one test function even if you use different functions to test one function.