This weeks labwork will be about Heap data structure. You are given a heap.h header file which contains a HeapNode class and Heap class. You are going to implement a min-heap. 1. The insert function is given as two parts. The first part is using Heap property to find the suitable location to add the given data to the Heap. For this purpose the code given to you includes a stack to hold the 0 or 1 values to navigate through the Heap. For example, 1 4 2 7 6 8 In this heap, if insert is called the suitable location is the right child of the node 2. In order to find this, you can use the heap-size. In this example the heap size is 6, when a new node is added the size will become 7. In order to navigate through the heap and find the location of the right child of 2, you must start from root and go right and right again to arrive at the proper location. If you find the mod 2 of 7 it is 1 so it points to the right. Then you perform integer division of 7 by 2 to find 3. This points to right again. This process is given in the insert function. You must use this stack and add the given data to the heap. Then fix the heap if the added data breaks the min-heap property. (70 pts) insert(const T &new_data) insert(const T &new_data, HeapNode *node, stack &dir) 2. You must write the necessary code to navigate the heap using level order. Print the heap so that the min-heap structure can be verified. print_levelorder(HeapNode *node, int level)

heap.h

#include #include #include

using namespace std;

template class HeapNode { public: T data; HeapNode *left; HeapNode *right; HeapNode *parent;

HeapNode(const T &new_data) { data = new_data; left = NULL; right = NULL; parent = NULL; } };

template class Heap { private: HeapNode *root; int node_count; public: Heap();

// These functions will be implemented recursively. The following are driver functions // for the programmer to use. void insert(const T&); void print_inorder() const; void print_levelorder() const;

private: HeapNode* insert(const T&, HeapNode*, stack&); void print_inorder(HeapNode*) const; void print_levelorder(HeapNode*, int) const; void swap(T*, T*); };

template Heap::Heap() { root = NULL; node_count = 0; }

template void Heap::insert(const T &new_data) { if (root == NULL) { root = new HeapNode(new_data); } else { node_count++; int tmp = node_count; stack dir; if (tmp > 2) { while (tmp != 1) { dir.push(tmp % 2); tmp = floor(tmp / 2); } } else { dir.push(0); } HeapNode *tmp_node = insert(new_data, root, dir); // Fix min-heap if the newly inserted element breaks min-heap property // percolate up ( Repeatedly exchange node with its parent if needed ) /* * * * * */ } }

template HeapNode* Heap::insert(const T &new_data, HeapNode *node, stack &dir) {

/* * * * * * * */ return tmp; }

template void Heap::print_inorder() const { print_inorder(root); std::cout << std::endl; }

template void Heap::print_inorder(HeapNode *node) const { if (node) { print_inorder(node->left); std::cout << node->data << " "; print_inorder(node->right); } }

template void Heap::print_levelorder() const { int h = floor(log2(node_count)) + 1; int i; for (i = 1; i <= h; i++) { for (int a = 0; a <= h - i; a++) { printf(" "); } print_levelorder(root, i); printf(" "); } }

template void Heap::print_levelorder(HeapNode *node, int level) const { /* * * * * * * */ }

template void Heap::swap(T *x, T *y) { T temp = *x; *x = *y; *y = temp; }

Main.cpp

#include "heap.h"

int main() {

Heap tree;

tree.insert(5); tree.insert(2); tree.insert(7); tree.insert(8); tree.insert(6); tree.insert(4); tree.insert(1); tree.insert(9);

tree.print_levelorder(); tree.print_inorder();

return 0; }