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 ...
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 ...
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 ...
Top 50 recent answers are included
Related Tags
heaps × 233data-structures × 129
algorithms × 79
binary-trees × 35
algorithm-analysis × 29
priority-queues × 24
runtime-analysis × 23
sorting × 20
time-complexity × 19
trees × 17
heap-sort × 16
arrays × 12
asymptotics × 10
amortized-analysis × 10
complexity-theory × 6
combinatorics × 6
graphs × 5
big-o-notation × 5
binary-search-trees × 4
dijkstras-algorithm × 4
search-algorithms × 3
shortest-path × 3
stacks × 3
comparison × 3
selection-problem × 3