I got an assignment to create a new data structure, with the following rules:
- Init - O(1).
- Insert x - O(log$_2$n).
- Delete x - O(log$_2$n).
- Search for x- O(log$_2$n).
- Find max difference between two values in the DS - O(1).
- Find min difference between two values in the DS - O(1).
I've outlined the basics of the structure to look somewhat like an array/arryaList in which I can complete the tasks using heap-like methods, and that way I'll be able to complete 1-4 in the times given.
Regarding 5 - I need to return the difference between the maxVal and minVal of the array, so it'll be the first number (arr) and I'll change the leaves to be so that the max is the last value (a[n-1]), and then I'll be in O(1).
Regarding 6, and this is where I'm stuck - how can I find the smallest difference between two values in O(1) time? I don't know of any methods that accomplish the task in O(1)...