Hi. This is more conceptual for me, but I am building a data structure that functions similarly to a mappinig. it has a key and value, but I cannot use the mapping or any other java library. I need to be able to locate an element in O(log n) time (which leads me to want to use binary search), but if I wanted to go about it using that, I'd need to be able to keep the array sorted as I add elements, but I can't efficiently do that without the threat of having to eventually add an element to the beginning, which would not be efficient. Is there no other way around it, or am I missing something?
#Create my own map
still citrus
split spruceBOT
⌛ This post has been reserved for your question.
Hey @still citrus! Please use
/closeor theClose Postbutton above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.
TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.
south lily
you could make a heap of key-value pairs
still citrus
I can't use any of the java included libraries
disregard I'm looking it up
I can't use this
wait
yea it would've been a better idea, but I am unsure if I am allowed to use a tree for this portion
since there's another part later on that requires the use of a tree, and I can't make a new file for the node that this would need
quaint pagoda
Hi. This is more conceptual for me, but I am building a data structure that func...
if you need to use arrays, you could create something like sorted arraylist, and store elements in the array with some offset for the first element. So at start the first element is stored, let's say, in 10th index. That gives you ability to insert elements and copy much less elements (not more than half of size).
And when you filled the first or last element in the array - you do enlargement
still citrus
That would be useful, but then the question becomes what about the middle elements? Would those elements have to be added in, accounting for the displacement of the other elements manually?
still citrus
if you need to use arrays, you could create something like sorted arraylist, and...
^
quaint pagoda
^
what you mean manually?
You count not from 0, but from the starting index (you need to store it). Same with last. Not sure I got your question
still citrus
I mean if I were to have an int array of like [1, 2, 4, 5] and I wanted to insert something like 3, it would displace 4 and 5, regardless of the padding on both the beginning and the end indexes
quaint pagoda
I mean if I were to have an int array of like [1, 2, 4, 5] and I wanted to inser...
that's how arraylist works
quaint pagoda
np.
so make your own
still citrus
as of rn, I'm trying to make that implementation
still citrus
I mean if I were to have an int array of like [1, 2, 4, 5] and I wanted to inser...
but I'm making sure this would be the best way to go about it because of this type of problem
though they aren't testing the efficiency of the add function, I wanted to be safe on trying it
south lily
By heap, I meant create your own heap data structure
Heaps are naturally sorted, and if you need a value for each sorted key, that works out well
still citrus
What I saw when I searched it up is a kind of tree structure
south lily
Yeah but just read the Wikipedia page on it or something, it's not that hard, even in C
still citrus
But I'd need a new file for the nodes to create it
still citrus
ok.
south lily
It can be implemented trivially using a flat array if you need
quaint pagoda
I have to say, that heap data structure is not sorted, and you can't find any element in it for O(log n )
quaint pagoda
Hi. This is more conceptual for me, but I am building a data structure that func...
by locating you meant finding, right?
still citrus
by `locating` you meant finding, right?
yea
But since I can use the heap, what I plan to do is have a heap of 2 element arrays which are key and value
oh wait
south lily
Just have a heap of "item"s, and then you have O(log n) lookup time since it's pre-sorted, if you know the key
And each item is a class with a key and value
still citrus
even if it's pre-sorted, How could I look it up?
south lily
Just start at the root, compare it to your key, and then check either the left or right child
And keep looking until there are no children or you find a matching item
still citrus
Wouldn't that still end up with O(n) time?
quaint pagoda
heap is not binary search tree, and it's not sorted in a way to lookup for any element in O(log n)
still citrus
what alexanderr said