lab_heaps

Assignment Description

In this lab you will write some heap functions to implement a min heap from scratch.

The version of heap you will implement will have a tree implemented in an array. Your array can be 0-index or 1-indexed, where 0 and 1 are the indices of the root, depending on which one you choose.

The left and right children of the root will be at the positions immediately after the root. For example, if your root is at index 0, its left child will be at index 1 and its right will be at index 2. The root’s left children will be at positions 3 and 4, and the root’s right children will be at positions 5 and 6, and so on and so forth. You will need to determine the indices to store these children in leftChild() and rightChild(), and the indices of each element’s parent in parent().

Remember that the big idea about a heap is that it must keep its heap property. In a min heap, this means that each element is smaller than both of its children. A max heap is the opposite- each element is larger than both of its children. Your maxPriorityChild() function will return the min child (out of an element’s left and right children) in a min heap and the max child in a max heap. This is not a recursive function- it simply utilizes the higherPriority functor and returns whichever child out of the two is less than or greater than the other, depending on what the priority for this heap is. Your heapifyUp() and heapifyDown() functions will ensure the heap property of your heap, by swapping elements recursively up or down the tree to maintain the heap property.

Lab Insight

Heap is an incredibly important data structure for prioritization functionality. Its performance in prioritization helps us implement path-finding algorithms efficiently. This same data structure is what helps power your navigation systems when you are trying to get from one place to another. To learn more about the practical importance of heaps, CS 374 and CS 473 delves into the applications of them in algorithmic contexts.

Checking Out the Code

All assignments will be distributed via our release repo on github this semester. You will need to have set up your git directory to have our release as a remote repo as described in our git set up

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main
git push

if you are using multiple machines you may need to use the following to allow them to work correcly.

git pull --no-edit --no-rebase release main --allow-unrelated-histories
git push

The first git command will fetch and merge changes from the main branch on your remote repository named release into your personal. The --no-edit flag automatically generates a commit message for you, and the--no-rebase flag will merge the upstream branch into the current branch. Generally, these two flags shouldn’t be used, but are included for ease of merging assignments into your repo.

The second command will push to origin (your personal), which will allow it to track the new changes from release.

You will need to run these commands for every assignment that is released.

All the files for this lab are in the lab_heaps directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the lab_heaps directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

The code for this activity resides in the lab_heaps/ directory. Get there by typing this in your working directory:

cd lab_heaps/

Check out the Doxygen for provided files.

root()

Doxygen for root(). Returns the index of the root- 0 for a 0-indexed heap, 1 for 1-indexed.

leftChild()

Doxygen for leftChild(). Returns the index of the left child of the element.

rightChild()

Doxygen for rightChild(). Returns the index of the right child of the element.

parent()

Doxygen for parent(). Returns the index of the parent of the element.

empty()

Doxygen for empty(). Determines if your heap is empty.

hasAChild()

Doxygen for hasAChild(). Determines if the current element has a child (aka if it isn’t a “leaf node”).

maxPriorityChild()

Doxygen for maxPriorityChild(). Determines the child with the maximum priority.

heapifyDown()

Doxygen for heapifyDown(). Maintains heap property by “sinking” a node down. When we pop an element, we heapifyDown() the new root so the heap’s property is maintained.

heapifyUp()

Maintains heap property by “bubbling” a node up. When a node is added to the end of the array, we call heapifyUp() to recursively swap it into its proper place. We have written this for you as an example: Doxygen for heapifyUp().

heap()

Doxygen for Constructor for building an empty heap. Doxygen for Constructor for building a heap.

pop()

Doxygen for pop(). Pops the element with the highest priority, as defined by the higherPriority functor. Maintains heap property by calling heapifyDown().

peek()

Doxygen for peek(). Returns the element with the highest priority.

push()

Doxygen for push(). Pushes an element into the heap, then calls heapifyUp() to maintain heap property.

updateElem()

Doxygen for updateElem(). Updates element in the heap array at the provided index (this is root()-indexed, so will work if using either zero or one-indexed heaps) while maintaining the heap property by appropriately “bubbling” up or down as need be. The index is relative to the first element in the heap, NOT necessarily the first element in the vector/array you are using for implementing the heap.

Testing Your Code

You can test your implementation by running:

./heaps           // Runs testheap with random inputs.
./heaps fixed     // Runs testheap with fixed inputs. You can diff the output with soln_testheap.out
./heaps color     // Colorizes the output of testheap (green for correct output
                      //    red for incorrect output, or red underlines for missing output)
./heaps fixed > out.txt // Redirects the output to the file "out.txt" so you can diff it with soln_testheap.out
./heaps 10000     // Tests your heap with 10000 items instead of the default 15

make test         // Tests your heapify and constructor

Grading Information

The following files (and ONLY those files!!) are used for grading this lab:

• heap.hpp
• heap.h

If you modify any other files, they will not be grabbed for grading! And you will be sad, and we will be apathetic!