Search for minor in log(n)

Asked

Viewed 29 times

0

Hello. I am in need of an efficient data structure to search for the lowest value of a disordered vector, being that:

  • The vector cannot be ordered.
  • The vector should be able to update the values in log(n).
  • The search for the lowest vector value should be in log(n).

Is there any data structure that meets the requirements?

Thank you in advance for the reply and the examples :)

c

  • A min heap meets these requirements, although not properly "disorderly"

  • Since the vector cannot be ordered later, I have a question: you can insert the item so that it is already ordered?

1 answer

3

Dude, it’s not possible without using some other structure. Because since it’s disorderly, you’ll only be sure you found the minor 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).

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.