Description
1 Assignment Overview
For this project you will be implementing a heap. Rather than implementing either a min-heap or a maxheap, 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.
2 Assignment Deliverables
You must turn in completed versions of the following files:
• Heap.py
Be sure to use the specified file name and to submit your files for grading via Mimir before the project
deadline.
3 Assignment Specifications
Your task will be to complete the methods listed below:
• len
• peek
• insert
• extract
• extend
• clear
• iter
• replace
• 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.
1
replace simultaneously inserts a new item and removes the highest priority item (including potentially
the new item). It must be more efficient than calling insert followed by 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
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. replace should not
raise an IndexError because it can always return the provided item if the list is initally 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 greater than 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.
4 Assignment Notes
• Points will be deducted if your solution has warnings of any type.
• You have been supplied with stubs for the required methods. You must complete these methods to
complete the project. 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, is empty, 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 define a function that is not bound
to a particular identifier. These lambda expressions define which of two arguments has a higher priority.
Lambda expressions have been used for some the unit tests for some of the earlier projects.
2
• 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, set, and dict classes and all of their member functions.
3
