MUST BE DONE IN C++

Hashing is very useful if we are only interested in insert, delete, and find operations; e.g., delete (30) or insert (15) or find (-10). But a hash table provides no assistance for searches that depend on the order or rank of an element in a set, e.g., find the smallest element, delete the largest element, etc. For the latter type of operation, heaps are more appropriate. On the other hand, heaps do not support a general delete operation, e.g., delete (-10); they only support deleting the min element.

In this programming assignment, you will develop a compound data structure called Quash, which is composed of both a min-heap (priority queue) and a hash table. The Quash supports inserts, delete and lookup using its hash component, and deleteMin using its heap component. In particular, each element in the set will be inserted in both the heap and the hash table. You will need to include pointers in both directions between the 2 instances of the element in the heap and in the hash table.

A count should be stored along with each element, in order to allow insertion of more than one copy of the same element. When an element is inserted for the first time, its count is 1 and every subsequent insertion increments the count. On deletion, the count is decremented. When the count becomes zero due to a deletion, then the element is completely deleted.

Operations should be executed as follows:

• insert(i): Insert element i in both the heap and the hash table, and link them correctly. Your program should return either item successfully inserted, count = 1 or item already present, count = n, where n is the count for that item

• lookup (i): Use the hash table to determine if i is in the data structure. Your program should return either item found, count = n, where n is the count for that item or item not found.

• deleteMin: Use the heap to find the minimum element and decrement its count. If its count becomes zero, delete it from the heap and use the pointer to delete the element in the hash table. Your program should return the key value of the item deleted.

• delete(i): Use the hash table to determine where i is and decrement its count. If the count becomes zero, delete it from the hash table and use the pointer to delete it from the heap. (Note you will need to generalize the heap operations to support this internal delete operation.) Your program should return either item count decremented, new count = n, item successfully deleted or item not present in the table.

• print(): Print out the heap contents separated by a whitespace.

Some specific implementation issues: Assume all elements to be inserted are integers (but they can be negative). CANNOT USE and !!!! Use mod 43 as the hash function (You are not required to implement resize) For collision resolution, use separate chaining.

The operations to be performed will be passed to your program through argv[1], with each command separated by a comma. An example input (contained in argv[1]) would be as follows.

Sample Input insert 10, insert -50, insert 76, lookup 12, insert 12, lookup 12, insert 12, lookup 12, print, deleteMin, delete -50, print, delete 10, print, delete Min, print, delete 12, delete Min, print, delete Min Sample Output item successfully inserted, count = 1 item successfully inserted, count = 1 item successfully inserted, count = 1 item not found item successfully inserted, count = 1 item found, count = 1 item successfully inserted, count = 2 item found, count = 2 -50 10 76 12 min item -50 successfully deleted item not present in the table 10 12 76 item successfully deleted 12 76 min item = 12, count decremented, new count = 1 12 76 item successfully deleted min item 76 successfully deleted min item not present since table is empty Sample Input insert 10, insert -50, insert 76, lookup 12, insert 12, lookup 12, insert 12, lookup 12, print, deleteMin, delete -50, print, delete 10, print, delete Min, print, delete 12, delete Min, print, delete Min Sample Output item successfully inserted, count = 1 item successfully inserted, count = 1 item successfully inserted, count = 1 item not found item successfully inserted, count = 1 item found, count = 1 item successfully inserted, count = 2 item found, count = 2 -50 10 76 12 min item -50 successfully deleted item not present in the table 10 12 76 item successfully deleted 12 76 min item = 12, count decremented, new count = 1 12 76 item successfully deleted min item 76 successfully deleted min item not present since table is empty