Download Notebook

Homework 6¶

Due Thursday, November 24th 2020 at 11:59 PM.¶

Be sure to push the final version of your code to your GitHub repo. Follow the instructions on the course website.¶

Topics¶

Problem 0 (C++). Homework Workflow [10 pts]¶

Prerequisite

Problem 1 (C++): BST Extensions [30 pts]¶

Part A. Remove minimum node (deleteMin)
Part B. Remove node (deleteNode)
Part C. BST Traversal

Problem 2 (C++): Heaps [30 pts]¶

Part A. Build a heap
Part B. Modify a heap
Part C. Min/Max-heap

Problem 3 (C++): Priority Queue [30 pts]¶

Part A. Naive priority queue
Part B. Priority queue based on min-heap
Part C. Compare three implementations of a priority queue

Note: We provide template code for each of the homework problems to help you get started.¶

Problem 0: Homework Workflow¶

Once you receive HW5 feedback, you will need to merge your HW5-dev branch into master.

You will earn points for following all stages of the git workflow which involves:

3pts for merging HW5-dev into master
5pts for completing HW6 on HW6-dev
2pts for making a PR on HW6-dev to merge into master

Prerequisite Questions¶

We would like your feedback on the Auto-eD tool that you used in Homework 4. Follow this link and answer the questions.

Problem 1 [30 pts]: BST Extensions¶

This problem builds on Problem 2 (C++) of Homework 5 in which you wrote a binary search tree. This time, you will first write some more supporting functions for your BST and then write a class to perform traversals on it.

Put your code for this problem in a file titled binary_search_tree.hpp. Failure to follow this instruction will result in point deduction.

#ifndef BINARY_SEARCH_TREE_HPP
#define BINARY_SEARCH_TREE_HPP

/* system header files */
#include <iostream>

/* namespace */
using namespace std;

// BST Iteration Types
typedef enum {
    INORDER,
    PREORDER,
    POSTORDER
} ORDER;

/* ============================ */
/* Templated BSTNode Definition */
/* ============================ */
template <class T1, class T2>
class BSTNode {
  public:
    T1 key;
    T2 value;
    BSTNode *left, *right;

  public:
    /* Constructors */
    BSTNode(T1 key, T2 value) : left(nullptr),right(nullptr) {
        this->key = key;
        this->value = value;
    }
};

/* ============================= */
/* Templated BSTTable Definition */
/* ============================= */
template <class T1, class T2>
class BSTTable {
  public:
    BSTNode<T1,T2> *root;

    /* private methods */
    BSTNode<T1,T2>* insert(BSTNode<T1,T2> *node, T1 key, T2 value){
        if(node == nullptr) return new BSTNode<T1,T2>(key,value);

        if (key < node->key) {
            node->left = insert(node->left, key, value);
        } else if (key > node->key) {
            node->right = insert(node->right, key, value);
        } else {
            node->value = value;
        }
        return node;
    }

    BSTNode<T1,T2>* search(BSTNode<T1,T2> *node, T1 key){
        if(node == nullptr) return node;

        if (key == node->key) {
            return node;
        } else if (key < node->key) {
            node = search(node->left, key);
        } else {
            node = search(node->right, key);
        }
        return node;
    }

    BSTNode<T1,T2>* minNode(BSTNode<T1,T2> *node){
        // TODO: check if minimum node (think about children pointers), return if appropriate

        // TODO: search recursively subtree for minimum
    }

    BSTNode<T1,T2>* deleteMin(BSTNode<T1,T2> *node){
        //TODO: check if minimum node
        //  --> if so, save right child, delete node, return right child

        // TODO: delete recursively (HINT: overwrite left child through assignment)
    }

    BSTNode<T1,T2>* deleteNode(BSTNode<T1,T2> *node, T1 key){
        // TODO: check base case (nullptr), return if approapriate

        if (key < node->key) {
            // TODO: recursively delete 
            //   HINT: node->left = deleteNode(...);
        } else if (key > node->key) {
            // TODO: recursively delete
            //   HINT: node->right = deleteNode(...);
        } else {
            if (node->left == nullptr) {
                // TODO: save right child
                // TODO: delete this node
                // TODO: return right child
            } else if (node->right == nullptr) {
                // TODO: save left child
                // TODO: delete this node
                // TODO: right left child
            }

            /* Node with two children: Get the inorder successor (smallest in the right subtree) */

            // TODO: Get inorder successor (find the minimum node in right subtree)
            //   HINT: use minNode(...)

            // TODO: overwrite this node's key with inorder successor's key

            // TODO: Delete the inorder successor node using the minimum node's key (two steps up)
            //   HINT: node->right = deleteNode(...);
        }
        return node;
    }

    void preorder(BSTNode<T1,T2> *node){
        if (node != nullptr) {
            // TODO: implement (3 lines)
        }
    }

    void inorder(BSTNode<T1,T2> *node){
        if (node != nullptr) {
            // TODO: implement (3 lines)
        }
    }

    void postorder(BSTNode<T1,T2> *node){
        if (node != nullptr) {
            // TODO: implement (3 lines) 
        }
    }

  public:
    /* Constructors */
    BSTTable() : root(nullptr) {}

    /* class methods */
    void put(T1 key, T2 value){
        root = insert(root, key, value);
    }

    T2 get(T1 key){
        BSTNode<T1,T2> *node = search(root, key);
        if(node) {
            return node->value;
        } else {
            NULL;
        }
    }

    void deleteMin(){
        root = deleteMin(root);
    }

    void deleteNode(T1 key){
        root = deleteNode(root,key);
    }

    void display(ORDER order){
        switch (order) {
            case (INORDER):
                cout << "INORDER: ";
                inorder(root); cout << "\n";
                break;
            case (PREORDER):
                cout << "PREORDER: ";
                preorder(root); cout << "\n";
                break;
            case (POSTORDER):
                cout << "POSTORDER: ";
                postorder(root); cout << "\n";
                break;
        }
    }
};
#endif /* BINARY_SEARCH_TREE_HPP */

Part A [10 pts]: Remove minimum node (`deleteMin`)¶

Your task: Please implement the methods minNode and deleteMin in your BSTTable class. It takes a BSTNode as an argument. It will return the subtree with the smallest node (the node with the smallest key) removed.

In Part B of this problem, you will see that the minNode function will help us reduce the complexity of a related function called deleteNode.

Hint: Remember that the deleteMin function should modify the tree.

Hint: check out these slides, especially the BST node removal.

Demo `HW6-bst-test.cpp`¶

BSTTable<int,std::string> *t = new BSTTable<int,std::string>();
    t->put(5,"a");
    t->put(1,"b");
    t->put(2,"c");
    t->put(0,"d");
    t->display(INORDER);

    t->deleteMin();
    t->display(INORDER);

    t->deleteNode(2);
    t->display(INORDER);

Result:

INORDER: (0,d) (1,b) (2,c) (5,a)
INORDER: (1,b) (2,c) (5,a) 
INORDER: (1,b) (5,a)

Part B [10 pts]: Remove Node¶

The deleteNode(T1 key) method removes the node with the corresponding key. It delegates the function calls to deleteNode(BSTNode<T1,T2> *node, T1 key), which takes a node and a key as an argument and returns the subtree without the node whose key is key.

Your task: Add and implement the following to the BSTTable class:

BSTNode<T1,T2>* deleteNode(BSTNode<T1,T2> *node, T1 key){
        // TODO: check base case (nullptr), return if approapriate

        if (key < node->key) {
            // TODO: recursively delete 
            //   HINT: node->left = deleteNode(...);
        } else if (key > node->key) {
            // TODO: recursively delete
            //   HINT: node->right = deleteNode(...);
        } else {
            if (node->left == nullptr) {
                // TODO: save right child
                // TODO: delete this node
                // TODO: return right child
            } else if (node->right == nullptr) {
                // TODO: save left child
                // TODO: delete this node
                // TODO: right left child
            }

            /* Node with two children: Get the inorder successor (smallest in the right subtree) */

            // TODO: Get inorder successor (find the minimum node in right subtree)
            //   HINT: use minNode(...)

            // TODO: overwrite this node's key with inorder successor's key

            // TODO: Delete the inorder successor node using the minimum node's key (two steps up)
            //   HINT: node->right = deleteNode(...);
        }
        return node;
    }

The method should raise an error if no node whose key is key is found.

Part C [10 pts]: BST Traversal¶

During lectures we discussed three types of depth-first traversal (DFS): preorder, inorder, and postorder. In addition to the lecture notes, here is another reference: Tree Traversal.

Your task: Write the functions preorder, inorder, and postorder.

void preorder(BSTNode<T1,T2> *node){
    if (node != nullptr) {
        // TODO: implement (3 lines)
    }
}

void inorder(BSTNode<T1,T2> *node){
    if (node != nullptr) {
        // TODO: implement (3 lines)
    }
}

void postorder(BSTNode<T1,T2> *node){
    if (node != nullptr) {
        // TODO: implement (3 lines) 
    }
}

Demo of BSTTable Traversal Functions¶

BSTTable<int,std::string> *t = new BSTTable<int,std::string>();
t->put(5,"a");
t->put(1,"b");
t->put(2,"c");
t->put(0,"d");

t->display(INORDER);
t->display(PREORDER);
t->display(POSTORDER);

Result:

INORDER: (0,d) (1,b) (2,c) (5,a) 
PREORDER: (5,a) (1,b) (0,d) (2,c) 
POSTORDER: (0,d) (2,c) (1,b) (5,a)

Deliverables¶

binary_search_tree.hpp: should contain implementations for BSTTable, BSTNode, minNode, deleteMin, deleteNode. Additionally, traversals preorder, inorder, and postorder should be implemented.

Problem 2 [30 pts]: Heaps¶

This question is all about the binary heap data structure. A (binary) heap is a (nearly) complete binary tree; this means all of it's non-leaf nodes have exactly two children which makes it suitable to store in a compact and memory efficient array. Each node of the tree is an element in the array.

The two types of binary heaps are: min-heap and max-heap. The heap-property is the most important invariant that holds at every node in the tree and is dependent on the type of heap we consider. In a min-heap the heap-property states:

In an array-backed min-heap, $A$, the following relation holds for every node (other than the root), $A[i]$: $A[Parent(i)] \leq A[i]$
the root is the minimum element of the tree

For a max-heap, the above comparison between parent ($A[Parent(i)]$) and child node ($A[i]$) is reversed and the root represents the tree's maximum element.

Your objective by the end of the question is to implement a binary max- and min-heap that support the following operations:

heapify: maintains the max/min-heap property
build_heap: turns an unordered array into a valid max/min-heap
heappush: inserts an element into the heap
heappop: removes and returns the heap's minimum/maximum element

Hint: Play around with this Heap visualization tool to get an intuition of its inner workings.

Hint: For an overview of operations on Heaps see these Heap lectures.

Hint: See the Wikipedia Binary Heap Page for useful guidance on potential solutions.

Hint: your build_heap output does not have to be consistent with our demo printouts since heap element arrangements are not unique. Your heap should simply support the heap-property at every node but can yield a number of different permutations of elements at every level (which on an interesting side-note can be computed using Heap's Algorithm named after B. R. Heap)

Part A [10 pts] : Building a min-heap¶

Your task: implement the heapify and build_heap functions for a min-heap.

Hint: By the end of the problem, we want you to have both a min- and max-heap. To avoid code duplication, notice that the only function dependent on the heap-type are the ones that need to preserve the heap-property (i.e., whenever we compare parent and child node). You will be reminded of this later on in the problem.

Copy the following Heap skeleton into a file called heap.hpp and complete the implementation:

#ifndef HEAP_HPP
#define HEAP_HPP

/* system header files */
#include <iostream>

/* ========================= */
/* Templated Heap Definition */
/* ========================= */
template <class T>
class Heap {
  private:
    int size;
    T *array;

  public:
    /* Constructor */
    Heap<T>(int size_, T *array_) :
        size(size_),
        array(nullptr)
    {
        if (size_ > 0 && array_ != nullptr) {
            array = new T[size_];

            // copy input array
            for (int i = 0; i < size_; ++i) {
                array[i] = array_[i];
            }
        }
    }

    /* Destructor */
   ~Heap<T>(){
        if(array) delete array;
    }

    /* Class Methods */
    int getSize(){return this->size;}
    T* getArray(){return this->array;}
    int parent(int i){return (i-1)/2;}
    int left(int i){return (2*i + 1);}
    int right(int i){return (2*i + 2);}

    void swap(int idx1, int idx2){
        T tmp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = tmp;
    }

    void display(){
        for (auto i = 0; i < size; ++i) {
            std::cout << array[i] << " ";
        }
        std::cout << "\n";
    }

    /* maintains the min-/max-heap property */
    void heapify(){
        // TODO: implement
    }

    /* turns unordered array into a valid min-/max-heap */
    void build_heap(){
        // TODO: implement
    }

    /* Required Derived Class Methods */
    virtual bool compare(T a, T b) = 0;

    /* inserts a new element into the heap while maintaining its heap-property */
    void heappush(T v){
        // TODO: implement
    }

    /* remove the min/max element and return it to the caller */
    T heappop(){
        // TODO: implement
    }
};

template <class T>
class MinHeap : public Heap<T> {
  public:
    /* Constructor */
    MinHeap<T>(int size, T *array) : Heap<T>(size,array){this->build_heap();}

    bool compare(T a, T b){
       // TODO: implement compare function
    }
};

template <class T>
class MaxHeap : public Heap<T> {
  public:
    /* Constructor */
    MaxHeap<T>(int size, T *array) : Heap<T>(size,array){this->build_heap();}

    bool compare(T a, T b){
        // TODO: implement compare function
    }
};

#endif /* HEAP_HPP */

Demo of building a heap: `HW6-heap-test.cpp`¶

int numA = 8, numB = 10;
int A[numA] = {1,0,0,15,23,1,2,3};
int B[numB] = {4,-7,9,8,0,-3,8,7,22,21};

MinHeap<int> *minh = new MinHeap<int>(numA, A);
MaxHeap<int> *maxh = new MaxHeap<int>(numB, B);

std::cout << "MinHeap Expected: ";
std::cout << "0 1 0 3 23 1 2 15\n";
std::cout << "MinHeap Result:   ";
minh->display();

Result:

MinHeap Expected: 0 1 0 3 23 1 2 15
MinHeap Result:   0 1 0 3 23 1 2 15

Part B: Modifying a heap¶

Now that you can build a min-heap, we want to add some more useful functionality to it such as inserting and removing elements.

Your task: implement the methods heappush and heappop for your Heap class.

heappush: inserts a new element into the heap (while maintining its heap-property!)
heappop:
- this function should remove the heap's minimum element and return it to the caller
- Raise an error when trying to pop from an empty heap

Add the following methods to your Heap class from Part A and finish their implementation:

/* inserts a new element into the heap while maintaining its heap-property */
void heappush(T v){
    // TODO: implement
}

/* remove the min/max element and return it to the caller */
T heappop(){
    // TODO: implement
}

Part C: A Wild Max-Heap Appears¶

As hinted in Part A of this question most of the logic for building and modifying a binary heap is the same between min-heaps and max-heaps. The main difference between the two is the heap-property that has to hold for all nodes.

Your task: Extent your Heap class from Part A and Part B and create two classes, MinHeap and MaxHeap, according to the code skeleton below.

Notes¶

MinHeap and MaxHeap should be subclasses that implement the compare() method.
The compare() method should be used in your heapify and heappush methods to maintain the heap-property for the particular type of heap. The function should compare two node values and return True if the comparison VIOLATES the heap-property for your particular heap.

template <class T>
class MinHeap : public Heap<T> {
  public:
    /* Constructor */
    MinHeap<T>(int size, T *array) : Heap<T>(size,array){}

    bool compare(T a, T b){
       // TODO: implement compare function
    }
};

template <class T>
class MaxHeap : public Heap<T> {
  public:
    /* Constructor */
    MaxHeap<T>(int size, T *array) : Heap<T>(size,array){}

    bool compare(T a, T b){
        // TODO: implement compare function
    }
};

Deliverables¶

heap.hpp: Should contain the Heap, MinHeap and MaxHeap classes. The Heap class should be implemented as a base class as described in Part 2C.

Problem 3 [30 pts]: Priority Queue¶

A priority queue is an abstract data type that represents a set of elements where each element has some key associated with it (a priority). Dequeueing (i.e., removing) an element from the priority queue will return the element with highest (in a max-priority queue) or lowest (in a min-priority queue) key. Thus removing all elements of the priority queue will leave you with a sorted list. A priority queue gets its name from the fact that elements are inserted or removed with priority over others.

Our priority queue should support following three operations:

put: add an element to the set
get: retrieve and remove the element with the largest key (or smallest depending on the type of priority queue)
peek: this should return the largest element (or smallest depending on the type of priority queue)

In our priority queue implementation, the key of an element will be the element itself. In a min-priority queue, an element, X, has a higher priority compared to element, Y, if X < Y. Examples:

1 < 3 is True, so we assume 1 has higher priority

Note: elements in your queue should all be of the same data type. That is, comparisons between different data types do not need to be handled in your queue implementation.

Note: in a max-priority queue you would compare elements using > to compute higher priority.

In this problem you will be asked to implement two different versions of a min-priority queue.

Copy below code template into a file called priority_queue.hpp.

#ifndef PRIORITY_QUEUE_HPP
#define PRIORITY_QUEUE_HPP

/* system header files */
#include <iostream>

/* header files */
//#include "heap.hpp"

/* ================================== */
/* Templated PriorityQueue Base Class */
/* ================================== */
template <class T>
class PriorityQueue {
  protected:
    int size;
    int maxSize;
    T *array;

  public:
    /* Constructor */
    PriorityQueue<T>(int maxSize_) : maxSize(maxSize_), array(nullptr) {}

    /* Destructor */
   ~PriorityQueue<T>(){}

  public:
    /* ========================== */
    /* Overloadable Class Methods */
    /* ========================== */

    /* put should take in a value val and insert it at the end of the elements list. 
     * This method should raise an error if called after max_size is reached. 
     * Nothing should be returned.
     */
    virtual void put(T val){
        // TODO
    }

    /* get should remove the smallest value from elements and return it.
     * This method should raise an error if called on an empty queue. 
     */
    virtual T get(){
        // TODO
    }

    /* peek should return the smallest value in the queue.
     * This method should raise an error on an empty queue.
     */
    virtual T peek(){
        // TODO
    }

    virtual void display(){
        for (auto i = 0; i < size; ++i) {
            std::cout << array[i] << " ";
        }
        std::cout << "\n";
    }
};

template <class T>
class NaivePriorityQueue : public PriorityQueue<T> {
  public:
    /* Constructor */
    NaivePriorityQueue<T>(int maxSize) : PriorityQueue<T>(maxSize) {
        this->array = new T[maxSize];
    }

    /* Destructor */
   ~NaivePriorityQueue<T>(){
       if(this->array) delete this->array;
    }
};


template <class T>
class HeapPriorityQueue : public PriorityQueue<T> {
  private:
    /* Data Members */
    // TODO: MinHeap<T> *minheap;

  public:
    /* Constructor */
    HeapPriorityQueue<T>(int maxSize) : PriorityQueue<T>(maxSize) {
        // TODO: allocate minheap, assign this-array to minheap's array
    }

    /* Destructor */
    // TODO: destroy minheap

  public:
    /* ========================= */
    /* Overloaded Class Methods */
    /* ========================= */

    /* put should take in a value val and insert it at the end of the elements list.
     * This method should raise an error if called after max_size is reached.
     * Nothing should be returned.
     */
    void put(T val){
        // TODO: put should push the element to the heap (heappush)
    }

    /* get should remove the smallest value from elements and return it.
     * This method should raise an error if called on an empty queue.
     */
    T get(){
        // TODO: get should remove and return the root element of the heap (heappop)
    }

    /* peek should return the smallest value in the queue.
     * This method should raise an error on an empty queue.
     */
    T peek(){
        // TODO: peek should return the smallest element of your min-heap
    }
};

#endif /* PRIORITY_QUEUE_HPP */

Part A [10 points]:¶

A naive way to implement a priority queue is to use a plain old list. Inserting an element appends to the list and extracting an element scans the whole list before returning (and removing) the highest priority element (remember what highest priority means in our min-priority queue).

Your task: implement a min-priority queue class called NaivePriorityQueue

Use the template code in priority_queue.hpp (keep the same file name).

Your class NaivePriorityQueue should inherit the base class PriorityQueue.

PriorityQueue will be initialized with a maxSize which indicates the capacity (maximum number of elements allowed) of the priority queue.

Your NaivePriorityQueue class needs to implement the methods:

put should take in a value val and insert it at the end of the elements list. This method should raise an error if called after maxSize is reached. Nothing should be returned.
get should remove the smallest value from elements and return it.
peek should return the smallest value in the queue.

Raise an error in the following three cases:

put called on a full priority queue
get called on an empty priority queue
peek called on an empty priority queue

Demo: `HW6-priority-queue-test.cpp`¶

NaivePriorityQueue<int> q(2);
q.put(1);
q.put(2);

std::cout << "Peek: " << q.peek() << std::endl;
std::cout << "Get: " << q.get() << std::endl;
std::cout << "Get: " << q.get() << std::endl;

Result:

Peek: 1
Get: 1
Get: 2

Part B [10 points]: Heap-backed priority queue¶

A better way to implement a priority queue is to use a binary heap.

Your task: Implement a min-priority queue using a min-heap. You will use your own heap from question 2.

With the heappush and heappop methods from the Heap class, we can effectively treat a heap as a priority queue. If we are using a heap to implement a priority queue:

put should push the element to the heap (heappush)
get should remove and return the root element of the heap (heappop)
peek should return the smallest element of your min-heap (largest element in a max-heap)

Please implement your priority queue called HeapPriorityQueue. As in Part A please use PriorityQueue as your base class in the same file.

Raise an error when appropriate.

Part C [10 points]:¶

P3-C.cpp contains three funcions which will be used to compare performance of three implementations.

In this problem, we will motivate the use of a priority queue and make you investigate the impact of the underlying implementation choice.

Your task: compare the performance of NaivePriorityQueue, HeapPriorityQueue and std::priority_queue. Run tests of each function: stl_priority_queue, naive_priority_queue, and heap_priority_queue, using multiple maxSize values: 1024, 2048, 4096, 8096, 16384, 32768.

Use this will be the x-axis for your performance plot described below.

Make a line plot to compare the running time of NaivePriorityQueue, HeapPriorityQueue and STL Priority Queue for an increasing heap size. In the plot, you should have three curves: one for each queue implementation. You should plot the elapsed time against heap size.

Graph format:

Use logarithmic scale on the x-axis only
Label your x- and y-axes
Create a descriptive title
x-axis: Heap Size
y-axis: Elapsed Time in seconds

Save the plot as P3-C.png.

Copy below code template into a file called P3-C.cpp.

#include <iostream>
#include <ctime>
#include <queue>
#include "priority_queue.hpp"

void showpq(std::priority_queue<int> gq){
    //std::priority_queue<int> g = gq;
    while (!gq.empty()) {
        std::cout << ' ' << gq.top();
        gq.pop();
    }
    std::cout << '\n';
}

double stl_priority_queue(int maxSize,int ntest=10){
   std::clock_t start;
   std::clock_t stop;

   // Reference: https://en.cppreference.com/w/cpp/container/priority_queue
   // Tutorial:  https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/

   /* Priority queues are a type of container adapters, specifically designed 
    * such that the first element of the queue is the greatest of all elements 
    * in the queue and elements are in non increasing order (hence we can see 
    * that each element of the queue has a priority {fixed order}).
    */

    // Defined in header <queue>
    // template<class T,
    //          class Container = std::vector<T>,
    //          class Compare = std::less<typenameC ontainer::value_type>
    //          >class priority_queue;

    std::priority_queue<int> stlpq;
    std::cout << "+============ STL PRIORITY QUEUE ============+\n";

    double total = 0.0;
    start = std::clock();
    for (int t = 0; t < ntest; ++t) {
        for (int i = 0; i < maxSize; ++i) 
            stlpq.push((13*i+512)%maxSize);

        for (int i = 0; i < maxSize; ++i) 
            stlpq.pop(); 
    }
    stop = std::clock();
    return (((stop - start) / (double) CLOCKS_PER_SEC)/(double) ntest);
}

double naive_priority_queue(int maxSize,int ntest=10){
    std::clock_t start;
    std::clock_t stop;

    NaivePriorityQueue<int> pq(maxSize);
    std::cout << "+============ Naive PRIORITY QUEUE ============+\n";

     double total = 0.0;
     start = std::clock();
     for (int t = 0; t < ntest; ++t) {
         for (int i = 0; i < maxSize; ++i)
             pq.put((13*i+512)%maxSize);

         for (int i = 0; i < maxSize; ++i)
             pq.get();
     }
     stop = std::clock();
     return (((stop - start) / (double) CLOCKS_PER_SEC)/(double) ntest);
}


double heap_priority_queue(int maxSize,int ntest=10){
    std::clock_t start;
    std::clock_t stop;

    HeapPriorityQueue<int> pq(maxSize);
    std::cout << "+============ HEAP PRIORITY QUEUE ============+\n";

     double total = 0.0;
     start = std::clock();
     for (int t = 0; t < ntest; ++t) {
         for (int i = 0; i < maxSize; ++i)
             pq.put((13*i+512)%maxSize);

         for (int i = 0; i < maxSize; ++i)
             pq.get();
     }
     stop = std::clock();
     return (((stop - start) / (double) CLOCKS_PER_SEC)/(double) ntest);
}

int main(int argc, char **argv){
    int maxSize = 16384;

    // TODO: test maxSize = {1024, 2048, 4096, 8096, 16384, 32768}
    // TODO: Plot comparing the three priority queues

    double stl_time = stl_priority_queue(maxSize,100);
    std::cout << "STL PQ Time Average: " << stl_time << "\n";

    double npq_time = naive_priority_queue(maxSize,100);
    std::cout << "Naive PQ Time Average: " << npq_time << "\n";

    double hpq_time = heap_priority_queue(maxSize,100);
    std::cout << "Heap PQ Time Average: " << hpq_time << "\n";

    return 0;
}

Deliverables¶

priority_queue.hpp: should contain NaivePriorityQueue, HeapPriorityQueue and PythonHeapPriorityQueue
P3-C.cpp: should contain the code for Part C
P3-C.png: should contain a plot comparing the three priority queue runtimes

Homework 6¶

Due Thursday, November 24th 2020 at 11:59 PM.¶

Be sure to push the final version of your code to your GitHub repo. Follow the instructions on the course website.¶

Topics¶

Problem 0 (C++). Homework Workflow [10 pts]¶

Problem 1 (C++): BST Extensions [30 pts]¶

Problem 2 (C++): Heaps [30 pts]¶

Problem 3 (C++): Priority Queue [30 pts]¶

Note: We provide template code for each of the homework problems to help you get started.¶

Problem 0: Homework Workflow¶

Prerequisite Questions¶

Problem 1 [30 pts]: BST Extensions¶

Part A [10 pts]: Remove minimum node (deleteMin)¶

Demo HW6-bst-test.cpp¶

Part B [10 pts]: Remove Node¶

Part C [10 pts]: BST Traversal¶

Demo of BSTTable Traversal Functions¶

Deliverables¶

Problem 2 [30 pts]: Heaps¶

Part A [10 pts] : Building a min-heap¶

Demo of building a heap: HW6-heap-test.cpp¶

Part B: Modifying a heap¶

Part C: A Wild Max-Heap Appears¶

Notes¶

Deliverables¶

Problem 3 [30 pts]: Priority Queue¶

Part A [10 points]:¶

Demo: HW6-priority-queue-test.cpp¶

Part B [10 points]: Heap-backed priority queue¶

Part C [10 points]:¶

Deliverables¶

Part A [10 pts]: Remove minimum node (`deleteMin`)¶

Demo `HW6-bst-test.cpp`¶

Demo of building a heap: `HW6-heap-test.cpp`¶

Demo: `HW6-priority-queue-test.cpp`¶