## Description

Priority queues (100 points)

You are asked to implement a binomial queue (bq) linked with a hash-table. You can use code

provided in the textbook. The bq is used for fast access of the minimum element and the hash-table

for fast access within the elements in the bq.

(1) Implement the binomial queue. For testing use the strings in the document file used in the

previous assignment. These would be the keys to be inserted into the priority queue.

Implement a hash-table of the keys that are already in the priority queue. So, for any pair

the key, and store the pair

deleteMin, or merge the hash-table needs to be updated as well. As part of this

implementation you have to create a private function

This function will return the pointer p that points to the node of bq that holds the key, or

nullptr if key is not in the bq.

(2) Count and print out the total number of comparisons and assignments executed for the

insertions of all the N elements into the binomial queue.

(3) Test the deleteMin() operation by applying a sequence of 10 deleteMin() and by printing out

the result.

(4) Test the function find() as follows: Prompt the user to input a string key. Execute the private

function find(key). If find returns a pointer to a node that indeed holds key printout that

find() was successful. Otherwise, printout that find() did not find the key.

(5) You are ready to implement now the remove(key) operation. For a given key, find its

position p (p is a pointer) in the priority queue using the hash table. If the key is found delete

it from the bq (Hint: your code should percolate the key up all the way to the root and then

delete the root). Test your implementation by applying a sequence of remove(key)

operations, and verify their correctness. For instance after remove(key), find(key) should

return “not found”. Prompt the user 5 times to input a key. Execute then the remove(key)

operation and verify (by printing whether the removal was successful or not).

(6) Write a faster insert(key) function for the binomial queue. In order to achieve that you have

to modify the merge() function and make it specific to the merging of one element only.