Lab 8: Heaps (100 pts)
Due Monday, June 4 at 9:20am on Canvas


Pair Programming Extra Credit Opportunity (5 pts)
  • Both partners fill in, sign, date, and submit the pair programming contract
  • Upload the document(s) along with your Lab to Canvas.
  • Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL THE FILES.


Part 1: Tutorial on Vectors
  • Although you may not have studied vectors in the past, they are a commonly-used part of the C++ language.
  • I would like you to learn how to use them before you leave 22C.
  • Also, they will be very useful in our Heap data structure, as we will use a vector to represent the Heap.
  • Therefore, it is time to learn about vectors if you never have before.
  • Don't worry! Vectors are easy - actually easier to use than arrays, as there are many things that vectors do for you.
    • In fact, a vector is simply a managed array
  • To start, look over the vector tutorial here.
  • If you would like further explanation, you can watch this video here.
  • Also, take a look at the member functions for this class here

Part 2: Heap Implementation (75 pts)
  • Copy the below code into a new header file called Heap.h
  • Then, create a new source code file called Heap.cpp.
  • Since we are not using templates, we are going to write our function definitions inside of the Heap.cpp.
  • We will test them in HeapTest.cpp.
Heap.h file:

#ifndef HEAP_H_
#define HEAP_H_

#include <vector>
#include <iostream>
using namespace std;

class Heap {
private:
    int heap_size;
    vector<int> *heap;

    /**Helper Functions*/

    void heapify(int i);
    //helper function to build_heap, remove, and sort
    //bubbles an element down to its proper location within the heap

    void heap_increase_key(int i, int key);
    //helper funciton to insert
    //bubbles an element up to its proper location

public:

    /**Constructors*/

    Heap(vector<int> &v);
    //assigns heap to point to v, an unordered array
    //calls build_heap to convert the unordered array into a valid max heap

    /**Manipulation Procedures*/

    void build_heap();
    //Takes an unordered vector and builds it into a heap
    //Called as a helper function of the constructor
    //Calls heapify as a helper function

    void insert(int value);
    //Inserts a new value onto the end of the heap and
    //Bubbles it up to the correct location in the heap
    //Calls heap_increase_key as a helper function

    void remove(int index);
    //removes the node at the provided index of the heap
    //pre: 1 <= i <= get_size()

    vector<int> sort();
    //sorts a heap into ascending order
    //returns the sorted array of values
    //post: heap restored to max heap
    //calls build heap as a helper function
    //calls heapify as a helper function

    /**Access Functions*/

    int get_max() const;
    //returns the maximum value in the heap
    //pre: heap_size > 0

    int get_parent(int i) const;
    //returns the location (index) of the parent of the element stored at index i
    //pre: 0 < i <= heap_size

    int get_left(int i)  const;
    //returns the location (index) of the left child of the element stored at i
    //pre: 0 < i <= heap_size

    int get_right(int i)  const;
    //returns the location (index) of the right child of the element stored at i
    //pre: 0 < i <= heap_size

    int get_size() const;
    //returns the heap_size (current number of elements

    int get_element(int i) const;
    //returns the element at the specified index i
    //pre: 0 < i <= heap_size

    /**Additional Operations*/

    void displayHeap(ostream& out) const;
    //prints the heap in level order
    //Hint: level = floor(log2(i) + 1)

    void displayArray(ostream& out) const;
    //prints each element in the array (heap) separated by a comma

};

#endif /* HEAP_H_ */


Part 3: File I/O and WriteHeap.cpp (25 pts)
  • Save two text files in the main project directory on Eclipse (right-click the name of the project and go to New->File).
    • If you followed the steps correctly, the text files will be placed in the main project folder, not in the src folder.
    • You can always drag and drop the files from src to the main project folder if you have made a mistake.
  • You can assume that the input file will be in divided into sections, as follows:
    1. An unordered array of values
    2. An index of an element to remove
    3. An element to insert
    4. Please see below for examples of formatting
  • You cannot assume any specific name for your input or output file, as these names will be specified by the user.
  • For each unordered array provided in the input file, you will want to do the following:
  1. Pass it to the heap constructor, which will build it into a valid heap
  2. Write the heap to the specified output file by calling displayHeap
  3. Remove the element at the index provided in the next line of the file
  4. Write the heap to the specified output file by calling displayArray
  5. Insert the element provided in the next line of the file
  6. Write the heap to the specified output file by calling displayArray
  7. Write the maximum value to the file
  8. Call sort and then write the returned vector to the output file to display sorted order
  • Please see below for examples of formatting.
  • Note that your formatting must exactly match what is shown for full credit.

Example Input File:

4 5 7 9 2 0 8 10 3
1
11
9 4 3 7 8 0 10 23 6 9 87 64 35 102 6 66 68 45 12 69 44
2
103
18 19 14 17 15 13
3
9
100 103 106 107 101 99 98 97 110 108
4
105
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
5
31

Matching Output File:
***********
Heap:
10
9 8
5 2 0 7
4 3

Removing 10:
9, 5, 8, 4, 2, 0, 7, 3

Inserting 11:
11, 9, 8, 5, 2, 0, 7, 3, 4

Maximum value: 11

In sorted order:
0, 2, 3, 4, 5, 7, 8, 9, 11

***********
Heap:
102
87 64
68 69 35 10
66 45 44 8 0 9 3 6
7 23 6 12 9 4

Removing 87:
102, 69, 64, 68, 44, 35, 10, 66, 45, 9, 8, 0, 9, 3, 6, 7, 23, 6, 12, 4

Inserting 103:
103, 102, 64, 68, 69, 35, 10, 66, 45, 44, 8, 0, 9, 3, 6, 7, 23, 6, 12, 4, 9

Maximum value: 103

In sorted order:
0, 3, 4, 6, 6, 7, 8, 9, 9, 10, 12, 23, 35, 44, 45, 64, 66, 68, 69, 102, 103

***********
Heap:
19
18 14
17 15 13

Removing 14:
19, 18, 13, 17, 15

Inserting 9:
19, 18, 13, 17, 15, 9

Maximum value: 19

In sorted order:
9, 13, 15, 17, 18, 19

***********
Heap:
110
108 106
107 101 99 98
97 103 100

Removing 107:
110, 108, 106, 103, 101, 99, 98, 97, 100

Inserting 105:
110, 108, 106, 103, 105, 99, 98, 97, 100, 101

Maximum value: 110

In sorted order:
97, 98, 99, 100, 101, 103, 105, 106, 108, 110

***********
Heap:
30
23 29
19 22 27 28
17 18 21 11 25 26 14 15
16 8 4 9 20 10 5 2 24 12 6 13 3 1 7

Removing 22:
30, 23, 29, 19, 21, 27, 28, 17, 18, 20, 11, 25, 26, 14, 15, 16, 8, 4, 9, 7, 10, 5, 2, 24, 12, 6, 13, 3, 1

Inserting 31:
31, 23, 30, 19, 21, 27, 29, 17, 18, 20, 11, 25, 26, 14, 28, 16, 8, 4, 9, 7, 10, 5, 2, 24, 12, 6, 13, 3, 1, 15

Maximum value: 31

In sorted order:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31

***********

Example Input File:

1 2 3 4 5
1
10
1000 999 998 997 996 995 994 993 992
2
991
75 45 85 95 35 25 65
3
105

Matching Output File:
***********
Heap:
5
4 3
1 2

Removing 5:
4, 2, 3, 1

Inserting 10:
10, 4, 3, 1, 2

Maximum value: 10

In sorted order:
1, 2, 3, 4, 10

***********
Heap:
1000
999 998
997 996 995 994
993 992

Removing 999:
1000, 997, 998, 993, 996, 995, 994, 992

Inserting 991:
1000, 997, 998, 993, 996, 995, 994, 992, 991

Maximum value: 1000

In sorted order:
991, 992, 993, 994, 995, 996, 997, 998, 1000

***********
Heap:
95
75 85
45 35 25 65


Removing 85:
95, 75, 65, 45, 35, 25

Inserting 105:
105, 75, 95, 45, 35, 25, 65

Maximum value: 105

In sorted order:
25, 35, 45, 65, 75, 95, 105

***********



WriteHeap.cpp

  • Your WriteHeap.cpp should work identically to the sample output below.
  • It should prompt a user for the name of a file and then use a loop to report an error if the file name is not found in the directory.
  • It should read in the contents of the file specified by the user
  • It should then prompt the user for the name of an output file and print the information as shown in the sample output files above into the output file:

Welcome to WriteHeap!

Please enter the name of the input file: 'rrays.txt
Invalid file name!

Please enter the name of the input file: arrays
Invalid file name!

Please enter the name of the input file: arrays.txt

***Reading from arrays.txt***

Please enter the name of the output file: heaps.txt

Thank you! Your heaps have now been written to heaps.txt!



How You Will Be Graded
  • 75 points for correctly-written heap functions
  • 25 points for a WriteHeap.cpp which can replicate the results of all example input and output files given for this assignment, plus any additional files with which the instructor may decide to test your code
  • 10 point deduction for a missing or incomplete HeapTest.cpp file
  • I will deduct points for operations that are not implemented as efficiently as possible.
    • In other words, be careful about when you are using build_heap vs heap_insert or build_heap vs heapify
    • Calling build_heap is more efficient than inserting a list of values into a heap one-by-one by calling insert.
    • Hint: an efficient remove can be performed in time O(logn).

What to Submit
  • Submit your Heap.cpp, WriteHeap.cpp, and HeapTest.cpp to Canvas.
  • Do not submit your Heap.h to Canvas.
  • Please submit each file separately (no zip files please).