I’m studying for my Computer Science class and need an explanation.
you recently reply to this question but somehow I can’t access on that account can you resend it
Project 5: Hashing & Heaps
Due: Tuesday, Dec 10, before 9:00 pm
Objectives
The objectives of this programming assignment are:
- To implement a heap and a hash table.
- To implement linear probing to handle hash collisions.
- To practice writing templated classes.
Background
For this project, you have to complete two templated classes:
- heap.h: the Heap class is a templated, vector-based heap implementation. This is a straight-forward implementation of a heap. Since it uses a vector rather than a C-style array to store the heap, you will not need to write a copy constructor, assignment operator, or destructor.
- hash.h: the HashTable class is a hash table implementation with a wrinkle — each bucket in the table is a heap! Collisions will be handled by linear probing. The array to store the hash table is a dynamically-allocated array (of heaps), so you will need to write a copy constructor, assignment operator, and destructor for this class.
Why would you ever want to build such a thing? I’m not sure you would, but here is a made-up application. Suppose you are a donut baker, and you distribute donuts to many different shops. You have a large number of donut types that you can bake — glazed, cinnamon, boston cream, bavarian cream, sprinkle, etc. — and lots of customers. Some of the customers are more important to you because they buy more donuts and always pay on time. You would like to record all your orders in the following way:
- First, you want to be able to search by donut type.
- Then, given the donut type, you always want to process the highest priority order first.
So, the donut type is the key for hashing purposes. All orders for a particular type will be stored in the same bucket, but the bucket will be a max-heap so that you can always retrieve the highest priority order quickly.
Once you see how the donut example works, it’s not too difficult to think of others. Suppose you want to track the repair priority of highway bridges. You want to search by highway name — US50, I97, I695, MD32, etc. — and, given the highway name, retrieve the bridge that is most in need of repair. The highway name is the hash key, and each bucket of the hash table is a max-heap using based on the repair priorities.
Since the Heap and HashTable classes are templated, it is easy to test them with either of the two examples given, or an example of your own. See the comments in hash.h for the requirements that the template class must satisfy and donut.h for an implementation of the donut example.
