Lab 8: Heaps (100 pts) Due Monday, June 4 at 9:20am on CanvasPair Programming Extra Credit Opportunity (5 pts)
Part 2: Heap Implementation (75 pts)
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)
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
Welcome to WriteHeap! ***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!
What to Submit
|