Consider the following problem: design a data structure that supports the following operations:
• insert(x): insert one copy of an element x,
• delete(x): delete one copy of an element,
• fi nd-mode(): return an element that occurs the most frequently (such an element is called a mode).
For example, after inserting 3, 1, 6, 3, 2, 6, 8, 6 to an initially empty data structure, fi nd-mode will return 6; and if we call delete(6) twice, then the next call to find-mode will return 3. Assume that all the elements are integers in the range {1,...,U}. Describe a data structure that can be preprocessed in O(U) time, can support insert and delete in O(log n) time, and can support fi nd-mode in O(1) time.
[Hint: maintain a count for each element in {1, ..., U} (like in counting sort). Then just use a heap (you do not need to re-describe how to do standard operations, e.g., delete-min/max and change-key, for the standard heap).]
[If you can, please improves the insert and delete time to O(1).]