Contents

Assignment: Heaps using Comptency-Based Grading

Assignment: Heaps using Comptency-Based Grading

NOTE: This is an abridged version of the lab handout, to see the full version, please visit the course site.

Motivation (Why are we doing this?)

The goal of this lab is to provide background on Heaps.

Background Info

Please see full lab handout for this section.

Your Task

NOTE: Please see full lab handout for file downloads.

Similar to last week’s lab, we give you a makefile, a unit test file, a doctest header file and a header file with class definitions for HeapNode and HeapTree classes (plus a couple other things). We have supplied heap.cpp to house your class definitions, and test.cpp will serve as your main file.

  • heap.h

  • heap.cpp

  • test.cpp

  • doctest.h

  • makefile

Requirements

Your goal for this lab is to complete the following tasks in order:

  1. Diagram the following operations for a min heap:

    • insert: 5, 3, 7, 2 , 4, 6, 8

    • remove_min

    • delete: 4

  2. Implement ‘min_heapify()’, ‘find_last()’, ‘remove_min()’, and ‘delete_element()’

  3. Copy your entire solution to a new Directory, and modify everything to create a max_heap

    • You will need to re-do the test cases in test.cpp!

Handing in

Please call a TA over to get checked off before leaving your lab section (regardless of how far you got). If you want to continue working on your lab after your lab section, come to hours to get checked off.

Grade Breakdown

This assignment covers heaps and balanced trees and your level of knowledge on them will be assessed as follows:

  • To demonstrate an awareness of these topics, you must:

    • Successfully meet requirements 1

  • To demonstrate an understanding of these topics, you must:

    • Successfully meet requirements 1 and 2

  • To demonstrate competence of these topics, you must:

    • Successfully meet requirements 1 through 3

previous

Scheme: Competency-Based Grading in Data Structures

next

Scheme: Specifications Grading in Data Structures