For this project you will be implementing a heap. Rather than implementing either a min-heap or a max-heap, yours will take a comparison function that determines which of two items has a higher priority. You will then use both a min-heap and a max-heap to find the median element of a sequence.

You must turn in completed versions of the following les:

Heap.py

Your task will be to complete the methods listed below:

len

peek

insert

extract

extend

clear

iter

find

median

Your implementation of len, and peek should run in constant time. Insert and extract should run in O (log n) time. Extend adds all of the elements in the given sequence to your heap and should run in O (n+m) time, where m is the number of items in the sequence. Clear removes all items from your heap and must run in O (n) time. Iter will enumerate all of the items in your heap and must run in O (n) time. The iterator is not required to traverse the items in any particular order except that the first item must be the next item that would be returned by a call to peek or extract. Find median determines the median (middle) item from a given sequence. If the length of the input sequence is even, you may return either of the median items arbitrarily. You should not compute the 1 average of the two medians as is normal for arithmetic sequences. Your find median function must be faster than sorting the sequence and finding the middle item. You must use heaps as part of your solution. The peek and extract methods should raise an IndexError if the heap is empty. Find median should also raise an IndexError if it is given an empty sequence. No other exceptions should be thrown. Your heap will determine the next item by using a comparison function, comp supplied to the heap in its constructor. comp(a, b) returns True if the priority of a is at least that of b and False otherwise. You should not use the natural ordering (that is the < operator) of the elements as this will prevent you from being able to use both min-heaps and max-heaps. You should use the natural ordering within the find median function. Duplicate items are allowed. You should include comments where appropriate. In particular, you should describe the overall method used to implement your heap and your strategy for find median. You must also add documentation for each of the above methods (as well as for any helper functions created) in the same style as for the pre-defined

methods.

Points will be deducted if your solution has warnings of any type.

You have been supplied with stubs for the required methods.

You may add more functions than what was provided, but you may not modify the signatures of the provided methods.

You do not have to worry about error checking for valid input. You may assume that the supplied reader function correctly reads the input file.

You do have to worry about accessing elements from an empty heap.

You must be able to handle duplicate elements. Duplicate elements are allowed.

Implementations for bool, isempty , and repr have been provided. Note that these rely on the len and iter functions, so you may want to complete these functions early.

You have been provided with some unit tests that can be used to assess your solution. There are additional test cases that will be kept hidden.

It is your responsibility to check for potential edge cases. The supplied unit tests do not account for all possible valid inputs

The comp property is a function pointer that determines the ordering of objects. You can invoke it with comp(a, b) just like you would for a regular function. It returns True if a has a higher priority than b. You should not use the objects' natural ordering within the Heap class (but you can for the find median function).

For the iter method, you may want to use the yield keyword.

The stub for the find median function creates both a min-heap and a max-heap by using lambda expressions (anonymous functions). The lambda keyword is used to de ne a function that is not bound to a particular identifier. These lambda expressions de ne which of two arguments has a higher priority. Lambda expressions have been used for some the unit tests for some of the earlier projects.

You may not modify the sequences passed to the extend or find median functions, but you may iterate over them.

The median items of the phonetic alphabet are `mike' and `november'.

You may not use any of the classes in the collections or heapq modules. You are allowed to use the list class and all of its member functions

******************************************************

PYTHON CODE:

class Heap: """ A heap-based priority queue Items in the queue are ordered according to a comparison function """

def __init__(self, comp): """ Constructor :param comp: A comparison function determining the priority of the included elements """ self.comp = comp # Added Members

def __len__(self): return 0

def peek(self): raise IndexError

def insert(self, item): pass

def extract(self): raise IndexError

def extend(self, seq): pass

def clear(self): pass

def __iter__(self): return iter([])

# Supplied methods

def __bool__(self): """ Checks if this heap contains items :return: True if the heap is non-empty """ return not self.is_empty()

def is_empty(self): """ Checks if this heap is empty :return: True if the heap is empty """ return len(self) == 0

def __repr__(self): """ A string representation of this heap :return: """ return 'Heap([{0}])'.format(','.join(str(item) for item in self))

# Added methods

# Required Non-heap member function

def find_median(seq): """ Finds the median (middle) item of the given sequence. Ties are broken arbitrarily. :param seq: an iterable sequence :return: the median element """ if not seq: raise IndexError min_heap = Heap(lambda a, b: a <= b) max_heap = Heap(lambda a, b: a >= b) raise IndexError

*******************************************************************

TEST CASES TO PASS: #!/usr/bin/python3

import unittest

from Heap import Heap, find_median

class TreeSetTests(unittest.TestCase):

def test_len(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] self.assertEqual(0, len(heap)) for index, item in enumerate(sequence): heap.insert(item) self.assertEqual(index + 1, len(heap))

def test_peek(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] min_items = [5, 5, 3, 3, 3, 2, 0, 0, 0, 0] self.assertRaises(IndexError, heap.peek) for item, min_item in zip(sequence, min_items): heap.insert(item) self.assertEqual(min_item, heap.peek())

def test_insert(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] min_items = [5, 5, 3, 3, 3, 2, 0, 0, 0, 0] self.assertRaises(IndexError, heap.peek) for index, (item, min_item) in enumerate(zip(sequence, min_items)): heap.insert(item) self.assertEqual(index + 1, len(heap)) self.assertEqual(min_item, heap.peek())

def test_extract(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] self.assertRaises(IndexError, heap.extract) for item in sequence: heap.insert(item) for index in range(len(sequence)): self.assertEqual(index, heap.extract()) self.assertRaises(IndexError, heap.extract)

def test_extend(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] copy = [x for x in sequence] heap.extend(sequence) self.assertEqual(10, len(heap)) heap.extend(sequence) self.assertEqual(20, len(heap)) for i in range(10): self.assertEqual(i, heap.peek()) self.assertEqual(i, heap.extract()) self.assertEqual(20 - 2 * i - 1, len(heap)) self.assertEqual(i, heap.peek()) self.assertEqual(i, heap.extract()) self.assertEqual(20 - 2 * i - 2, len(heap)) self.assertEqual(copy, sequence)

def test_median(self): self.assertRaises(IndexError, find_median, []) sequence = [5, 9, 3, 4, 6, 2, 8, 7, 1] copy = [x for x in sequence] self.assertEqual(5, find_median(sequence)) self.assertEqual(copy, sequence)

sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] copy = [x for x in sequence] self.assertIn(find_median(sequence), [4, 5]) self.assertEqual(copy, sequence)

def test_max(self): heap = Heap(lambda a, b: a >= b) sequence = [5, 3, 4, 6, 2, 0, 8, 9, 7, 1] max_items = [5, 5, 5, 6, 6, 6, 8, 9, 9, 9] self.assertRaises(IndexError, heap.peek) for item, max_item in zip(sequence, max_items): heap.insert(item) self.assertEqual(max_item, heap.peek())

def test_clear(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] heap.extend(sequence) self.assertFalse(heap.is_empty()) heap.clear() self.assertTrue(heap.is_empty()) self.assertRaises(IndexError, heap.peek) self.assertRaises(IndexError, heap.extract) heap.insert(9) self.assertEqual(1, len(heap)) self.assertEqual(9, heap.peek()) self.assertEqual(9, heap.extract()) self.assertTrue(heap.is_empty())

def test_iter(self): heap = Heap(lambda a, b: a <= b) sequence = [5, 9, 3, 4, 6, 2, 0, 8, 7, 1] heap.extend(sequence) dump = [x for x in heap] self.assertEqual(len(sequence), len(dump)) self.assertEqual(0, dump[0]) self.assertEqual(set(sequence), set(dump))

if __name__ == '__main__': unittest.main()