3 Maintaining Trails [8 points] Hikes need to be maintained as the more people visit them the more their conditions deteriorate. At the end of each day, smart meters installed at each trail send the number of hikers who have gone through each trail. The information for day d is sent to you as a list of tuples Ud where each tuple is of the form (i, h) where i is a trail number and h is the number of hikers who travelled on i today. The order in Ud is arbitrary and not specified while the size of Ud differs day to day. For this part, you can assume that there are ntrails trails numbered from 0 to ntrails - 1. Occasionally, the maintenance team sends a query asking for the number of the most travelled trail (if there is more than one, ties are broken arbitrarily). After the query, this trail is repaired. You propose to support the above query by maintaining the following max-heap H. Each node in the heap represents a trail and stores a counter of the number of hikers since last maintenance of that trail. The heap is updated everyday based on information in Ud. The most-travelled trail can be easily retrieved as it is the root node of the heap. When the maintenance query is sent, the counter of root node is reset to 0 and the heap needs to be "repaired". 1. [4 points] Describe an efficient way to update the heap H given Ud. Write pseudo-code of your solution UPDATEHEAP(H, Ud). A solution with non-optimal complexity may receive partial marks. 2. [4 points] Your colleague argues that using a max-heap is inefficient, and suggests to keep an array of counters indicating the number of hikers since last maintenance of each trail and update it every day using Ud. On each maintenance query, the array is scanned to find the most-travelled trail and its counter is then reset to 0. Let la denote the size of Ud. Indicate the time complexity of your approach and your colleague's approach, on the following two operations, respectively: (a) Update the data structures upon receiving Ud (b) Process a maintenance query (i.e., return the most travelled hike since last repair, reset its counter to 0 and update the corresponding data structures) Which approach would you prefer? Briefly justify your answer.