## Description

In this lab, you will explore one implementation of a priority queue. Additionally, you will implement a sorting

algorithm based on the data structure.

## 1 Maximum Binary Heap

1.1 Properties

A maximum binary heap is a binary tree structure (not a BST) with two additional properties:

• The structure property: a binary heap is a complete binary tree. This means that every level of the tree, except

possibly the last, is fully filled. The last level of the tree must be filled in from left to right.

• The heap property: the value at each node is greater than or equal to the values of its children. (Note that this

ordering would be reversed for a minimum binary heap.)

## 1.2 Our Implementation

Rather than reinvent array-based lists again, in this lab, you’ll be using Python lists with Python’s list methods

to store the underlying tree structure. You can (and should) use list.append(item) to add to the end of a list,

list.pop() to remove (and return) the last item in a list, and len(list) to return the length of a list.

You should not import any Python standard library modules into your code.

As discussed in class, index 0 of the list should be left blank to allow for easier formulas when “traversing” the tree.

## 1.3 Operations

You will implement the following operations for a maximum binary heap:

• enqueue This function takes a maximum binary heap and an item as arguments and adds the item to the heap

in the appropriate position. After the function finishes, the heap should still satisfy the above properties. This

function will not return anything.

This function should have O(log n) worst case and O(1) average case time complexity (as discussed in class).

• dequeue This function takes a maximum binary heap as an argument and removes (and returns) the largest

item from the heap. After this function finishes, the heap should still satisfy the above properties.

If the heap is empty, this function should raise an IndexError.

This function should have O(log n) worst case time complexity.

• peek This function takes a maximum binary heap as an argument and returns (without removing) the largest

item in the heap.

If the heap is empty, this function should raise an IndexError.

This function should have O(1) time complexity.

CPE 202 Lab 7, Page 2 of 2

• size This function takes a maximum binary heap as an argument and returns the number of items in the heap.

(Note that this will not be the size of the underlying list, but it will be close.)

This function should have O(1) worst case time complexity.

• _contents This function takes a maximum binary heap as an argument and returns a list of the contents of

the heap in the order they are stored in the heap’s internal list. The return value should only include the

“filled” spots in the list.

You may find this useful for testing.

Note that the leading underscore is not a typo. It’s generally bad practice for a function like this to exist, and

so we’re using the Python standard practice of a leading underscore to mean that it’s not meant to be used

directly by “users” of your MaxHeap structure. You should only be using this for testing.

While not explicitly specified, you will likely find it helpful to write separate functions for sifting (percolating)

up/down.

## 1.4 Other Functions

You will additionally implement the following functions related to the heap structure:

• heapify This function takes a list as an argument and builds and returns a maximum binary heap out of the

items in the list. The input list should not be modified in any way.

You should not implement this by repeatedly enqueuing each item in the list. Rather, you should use the

heapify algorithm discussed in class, where we repeatedly sift (percolate) items down, from the bottom up.

This function should have O(n) worst case time complexity.

• heap_sort This function takes a list as an argument and mutates the list to be sorted in ascending order. It

will do this by building a heap with the items in the list and them dequeuing them back into the given list.

This function should have O(n log n) worst case time complexity.

## 2 Testing

As mentioned in the syllabus, your code is periodically graded prior to the deadline and you will receive automated

feedback based on the results of my tests. But, in order to receive any feedback, your tests much provide 100% test

coverage of the code you are submitting. If you do not have 100% coverage, this is the only feedback you will receive.

100% test coverage means that every line of your code is run at some point in some test. Imagine if that weren’t the

case. That means that you have a line of code (or multiple lines of code) that could do anything, and you’d never

know. You never tested them!

Your tests will go in files named heap_tests.py.

## 3 GitHub Submission

Push your finished code back to GitHub. Refer to Lab 0, as needed, to remember how to push your local code.