Description
Summary and Specific Instructions
1. Implement the MinHeap class by completing the provided skeleton code in the file
min_heap.py. Once completed, your implementation will include the following
methods:
add()
is_empty()
get_min()
remove_min()
build_heap()
size()
clear()
heapsort()
2. The MinHeap must be implemented with a DynamicArray as per the skeleton code.
You are to use your existing DynamicArray for the implementation.
3. You may wish to augment your existing DynamicArray to assist you in this
assignment. For instance, a method similar to pop() in Python’s list, that removes
the last item in your DynamicArray, may be helpful. Alternatively, you may
implement this functionality inline in your heap implementation, if you prefer.
4. The number of objects stored in the MinHeap will be between 0 and 1,000,000
inclusive.
5. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods.
You are NOT allowed to directly access any variables of the DynamicArray class. All
work must be done only by using class methods.
6. You do not need to write any getter or setter methods for the MinHeap class.
7. Be sure to review your methods to make sure that they meet the runtime complexity
requirements.
8. You may not use any imports beyond the ones included in the assignment source
code provided.
Page 4 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
add(self, node: object) -> None:
This method adds a new object to the MinHeap while maintaining heap property.
The runtime complexity of this implementation must be O(log N).
Example #1:
h = MinHeap()
print(h, h.is_empty())
for value in range(300, 200, -15):
h.add(value)
print(h)
Output:
HEAP [] True
HEAP [300]
HEAP [285, 300]
HEAP [270, 300, 285]
HEAP [255, 270, 285, 300]
HEAP [240, 255, 285, 300, 270]
HEAP [225, 255, 240, 300, 270, 285]
HEAP [210, 255, 225, 300, 270, 285, 240]
Example #2:
h = MinHeap([‘fish’, ‘bird’])
print(h)
for value in [‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’]:
h.add(value)
print(h)
Output:
HEAP [‘bird’, ‘fish’]
HEAP [‘bird’, ‘fish’, ‘monkey’]
HEAP [‘bird’, ‘fish’, ‘monkey’, ‘zebra’]
HEAP [‘bird’, ‘elephant’, ‘monkey’, ‘zebra’, ‘fish’]
HEAP [‘bird’, ‘elephant’, ‘horse’, ‘zebra’, ‘fish’, ‘monkey’]
HEAP [‘bear’, ‘elephant’, ‘bird’, ‘zebra’, ‘fish’, ‘monkey’, ‘horse’]
Table of Contents Page 5 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
is_empty(self) -> bool:
This method returns True if the heap is empty; otherwise, it returns False.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([2, 4, 12, 56, 8, 34, 67])
print(h.is_empty())
Output:
False
Example #2:
h = MinHeap()
print(h.is_empty())
Output:
True
Page 6 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
get_min(self) -> object:
This method returns an object with the minimum key, without removing it from the heap. If
the heap is empty, the method raises a MinHeapException.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([‘fish’, ‘bird’])
print(h)
print(h.get_min(), h.get_min())
Output:
HEAP [‘bird’, ‘fish’]
bird bird
remove_min(self) -> object:
This method returns an object with the minimum key, and removes it from the heap. If the
heap is empty, the method raises a MinHeapException.
For the downward percolation of the replacement node: if both children of the node have
the same value (and are both smaller than the node), swap with the left child.
The runtime complexity of this implementation must be O(log N).
Example #1:
h = MinHeap([1, 10, 2, 9, 3, 8, 4, 7, 5, 6])
while not h.is_empty() and h.is_empty() is not None:
print(h, end=’ ‘)
print(h.remove_min())
Output:
HEAP [1, 3, 2, 5, 6, 8, 4, 10, 7, 9] 1
HEAP [2, 3, 4, 5, 6, 8, 9, 10, 7] 2
HEAP [3, 5, 4, 7, 6, 8, 9, 10] 3
HEAP [4, 5, 8, 7, 6, 10, 9] 4
HEAP [5, 6, 8, 7, 9, 10] 5
HEAP [6, 7, 8, 10, 9] 6
HEAP [7, 9, 8, 10] 7
HEAP [8, 9, 10] 8
HEAP [9, 10] 9
HEAP [10] 10
Table of Contents Page 7 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
build_heap(self, da: DynamicArray) -> None:
This method receives a DynamicArray with objects in any order, and builds a proper
MinHeap from them. The current content of the MinHeap is overwritten.
The runtime complexity of this implementation must be O(N). If the runtime complexity is
O(N log N), you will not receive any points for this portion of the assignment, even if your
method passes Gradescope.
Example #1:
da = DynamicArray([100, 20, 6, 200, 90, 150, 300])
h = MinHeap([‘zebra’, ‘apple’])
print(h)
h.build_heap(da)
print(h)
print(“Inserting 500 into input DA:”)
da[0] = 500
print(da)
print(“Your MinHeap:”)
print(h)
if h.get_min() == 500:
print(“Error: input array and heap’s underlying DA reference same object
in memory”)
Output:
HEAP [‘apple’, ‘zebra’]
HEAP [6, 20, 100, 200, 90, 150, 300]
Inserting 500 into input DA:
DYN_ARR Size/Cap: 7/8 [500, 20, 6, 200, 90, 150, 300]
Your MinHeap:
HEAP [6, 20, 100, 200, 90, 150, 300]
Page 8 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
size(self) -> int:
This method returns the number of items currently stored in the heap.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([100, 20, 6, 200, 90, 150, 300])
print(h.size())
Output:
7
Example #2:
h = MinHeap([])
print(h.size())
Output:
0
clear(self) -> None:
This method clears the contents of the heap.
The runtime complexity of this implementation must be O(1).
Example #1:
h = MinHeap([‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’])
print(h)
print(h.clear())
print(h)
Output:
HEAP [‘bear’, ‘elephant’, ‘monkey’, ‘zebra’, ‘horse’]
None
HEAP []
Table of Contents Page 9 of 10
CS261 Data Structures Assignment 5: MinHeap Implementation
heapsort(arr: DynamicArray) -> None:
Write a function that receives a DynamicArray and sorts its content in non-ascending order,
using the Heapsort algorithm. You must sort the array in place, without creating any data
structures. This function does not return anything.
You may assume that the input array will contain at least one element, and that values
stored in the array are all of the same type (either all numbers, or strings, or custom
objects, but never a mix of these). You do not need to write checks for these conditions.
The runtime complexity of this implementation must be O(N log N). If the sort uses an
algorithm other than Heapsort, you will not receive any points for this portion of the
assignment, even if your function passes Gradescope.
Example #1:
da = DynamicArray([100, 20, 6, 200, 90, 150, 300])
print(f”Before: {da}”)
heapsort(da)
print(f”After: {da}”)
Output:
Before: DYN_ARR Size/Cap: 7/8 [100, 20, 6, 200, 90, 150, 300]
After: DYN_ARR Size/Cap: 7/8 [300, 200, 150, 100, 90, 20, 6]
Example #2:
da = DynamicArray([‘monkey’, ‘zebra’, ‘elephant’, ‘horse’, ‘bear’])
print(f”Before: {da}”)
heapsort(da)
print(f”After: {da}”)
Output:
Before: DYN_ARR Size/Cap: 5/8 [monkey, zebra, elephant, horse, bear]
After: DYN_ARR Size/Cap: 5/8 [zebra, monkey, horse, elephant, bear]
Page 10 of 10
