SOLVED ECE 365 Programming Assignment #2

You are going to create a class called "heap" that provides programmers with the functionality of a priority queue using a binary heap (a.k.a. heap) implementation. Each item inserted into the binary heap will specify a unique string id, an integer key, and optionally any pointer. The implementation of the class should use pointers to void, in order to handle pointers to any type of data. When a heap is declared, a capacity will be passed to its constructor representing the maximum number of items that may be in the heap at one time; the heap will never be allowed to grow past its initial capacity (although it is simple to implement a resize operation). I have written a program that uses my own implementation of the class. I will provide you with that program (useHeap.cpp) and with a Makefile. You should not change my source code file! You are allowed to -std=add c++11 or other flags to the Makefile if you need to. Both files will be discussed in class and can be obtained from the course home page. Your heap will also make use of the hash table class that you created for the previous programming assignment. This assignment asks you to fill in the missing heap.cpp and heap.h files, and to correct or add to your hash.cpp file if necessary, so that everything works. This implies that your heap class must include at least the following: a constructor that accepts an integer representing the capacity of the binary heap; a public member function, insert, used to insert a new item into the heap; a public member function, deleteMin, that removes and returns the item with the lowest key from the heap; a public member function, setKey, providing both increaseKey and decreaseKey functionality; and a public member function, remove, that allows the programmer to delete an item with a specified id from the heap. In class we will discuss the parameters of these member functions and their return values. In addition, your class should contain private data members and private member functions that allow you to elegantly and efficiently implement the required public member functions. I will discuss my own implementation in class, and it is described on the next page. In class, we will look at a sample run of the program and discuss the provided code. This program only passes string ids and integer keys to the insert member function of the heap class, but again, the insert member function should also optionally accept any pointer that can be stored and associated with the id. In the future, you will be using the class you are creating for this assignment to implement an algorithm involving graph data structures, and this functionality will be necessary. Also, note that the integer keys will not necessarily be positive integers. All operations should be implemented using average-case logarithmic time (or better) algorithms. In order to achieve setKey and remove in average-case logarithmic time, your program needs to be able to map an id to a node quickly. Since each id can be any arbitrary string, a hash table is useful for this purpose. Searching a heap to find an item with a particular id would require linear time, but a hash table in which each hash entry includes a pointer to the associated node in the heap allows you to find the item in constant average time. Apart from the calls to the hash table member functions, which are worst-case linear time but average-case constant time operations, all heap operations should use worst-case logarithmic time algorithms, and the insert operation should use an average-case constant time algorithm. My heap class contains four private data members. Two are simple integers representing the capacity and the current size of the heap. The third is a vector of node objects containing the actual data of the heap; each node contains a string id, an integer key, and a pointer to void that can point to anything. (I made "node" a private nested class within the heap class.) The fourth private data member is a hash table. Since the heap constructor is provided with the maximum size of the heap, you may construct the hash table to be large enough such that there is a small likelihood of a rehash, but that is up to you (I'll discuss how to do that in class). Note that since items get removed from the heap, but only lazily deleted from the hash table, it is still possible that a rehash of the hash table will be necessary. Your heap.h file should contain the class definition of your heap class, including the declarations of its public and private data members and member functions. The heap.cpp file should contain the implementation of the class. I don't think you should need to implement any functions other than the member functions of the class in this file (I did not). As usual, you will be graded not only on the correctness of your program, but also on the appropriateness of the decisions that you make, the elegance (and perhaps the formatting) of your code, and on the appropriate use of C++ concepts and routines. The following page shows the declarations of the constructor and the public member functions of my heap class along with my comments describing their functionalities, parameters, and return values. I am not showing the declarations of my private data members or private member functions here, but I will provide certain additional excerpts from my code; these will be posted on the course webpage and discussed further in class.