New answers tagged heaps
3
votes
Accepted
Find the smallest difference between two numbers in a DS in O(1) time
Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the ...
- 170
1
vote
Find the smallest difference between two numbers in a DS in O(1) time
I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations.
A possible data structure consists of an AVL tree $T$ plus a priority ...
- 22.8k
1
vote
Find the smallest difference between two numbers in a DS in O(1) time
I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes:
the minimum difference between two leaves in the subtree;
the minimum and maximum values of a leaf in ...
- 7,154
Top 50 recent answers are included