Search for the child in log (n)

Question

Search for the child in log (n)

Navigation

#1 by (3 votes)

0

Hello. I need an efficient data structure to get the smallest value of a cluttered vector, where:

The vector can not be ordered.
The vector must be able to update the values in log (n).
The search for the smallest value of the vector must be in log (n).

Is there a data structure that meets the requirements?

I thank you for the answer and the examples:)

c

asked by anonymous 03.11.2018 / 01:29

1 answer

Help Update Laravel Option appearing in textarea separated by commas / lines

score 3 · Answer 1

Dude, it is not possible without using some other structure. For as it is disorderly, you will only be sure that you have found the smallest if you check all the values. But if you store in a structure like a tree, the values will already be stored in an orderly way. For the search in a disordered vector the worst case will always be O (n).