1
$\begingroup$

I've looked around and can't find my answer.

I have a set of $n$ numbers. In each iteration I would like to find an arbitrary number and change it. Is it possible to perform each iteration in $\log n$ time?

There are data structures like a min-max heap which allow insertion and deletion in $\log n$ time, but that only allows deletion on the min/max values.

$\endgroup$
1
$\begingroup$

Yes, you can achieve that running time if you use the right data structure. You might want to look at some other data structures, such as AVL trees, red-black trees, or other similar techniques. See, e.g., https://en.wikipedia.org/wiki/Search_data_structure, https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree, or your favorite data structures book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.