## 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