IMPLEMENT IN C++. PLEASE COMPLETE AS MUCH AS YOU CAN IF EVEN IFIT PART OF A CODE THAT IS FINE. ASAP! WIll be given thumbs up! Implement the ?rst level of cache as a Hash Table (HT) withlinear probing and the second level as a Max Heap (MH). Each dataelement has three ?elds: 1. address of the element (key) 2. valueof the element 3. priority of the element (representing itsimportance as in its frequency of recent accesses for a TLB).

When the user makes a query for an element, the HT is ?rst queriedusing the key. If there is hit, the user can access the valuepresent in the corresponding entry. If there is a miss, then theuser needs to look for the the element in the MH. The datastructure should support the following operations:

1. Load MH : Load the values from a speci?ed input ?le into the MH.The priorities are set to 0. HT is initially empty.

2. Load HT : Move the top k (size of HT) priority elements to HT.Some elements from the HT may need to be moved to the MH. If thepriorities are same, then the element with higher key value will bepresent in HT.

3. Access(key) : Find the speci?ed element, increase its priorityby 1 and print whether it is present in HT/MH along with value ofthe element. • Print format : (0/1/-1) a) 0 : if present in HT b) 1: if present in MQ c) -1 : if element is not present

4. Display : Returns all the elements present in the HT/MH.

Your Task

1. You should ?rst load, the data that is given to you into MaxHeap.

2. Then, you move the top k(size of HT) priority elements toHT.

3. Then, whenever query has been made access the speci?ed elementby above aforementioned process.

Remarks: First step to perform after reading all the inputs is LoadHT. Input hw1 q2 in.txt : This ?le contains the elements that needto be loaded followed by queries: 2 2 3 5 25 30 20 18 11 15 2 20 2 11 3 1 3 1 2 3 15 10 16 11 2 15 1 2 15 EXPLANATION OF THE INPUT: (a) First line : Number of test cases. (nT)

(b) Second line : HashTable size of the test case. (sHT)

(c) Third line : Number of inputs to be read for the testcase.(nI)

(d) Fourth line : Number of queries corresponding to the testcase.(nQ)

(e) Next ’nI’ lines contain elements of the test case • Format :¡address of the element¿ ¡value of the element¿ (Both items areseparated by space)

(f) Next ’nQ’ lines contains Query for the test case Format of thequery : • Load MH : 0 • Load HT : 1 • Access(key) : 2 • Display : 3(g) (b,c,d,e,f) steps are repeated ’nT’ times OUTPUT: You should output a ?le hw1 q2 out.txt. The contents of the output ?le should be answers to each queryin the input ?le. Output of Query Format : • Access(key) : (0/1/-1) ¡value of the element¿ – 2 numbers separated by a space : 1st number corresponds towhether the element is in HT/MH and second number corresponds tovalue of the element • Display : Two lines w.r.t each display query – First line corresponds to elements in HT. Elements should bespace separated. – Second line corresponds to elements in MH. Elements should bespace separated. • Output of each test case should be separated by an emptyline. • Note : Load HT, Load MH has no outputs . . .