0

I have been told to use an integer array and insert elements into it, which is relatively simple. The difficult part is having to expand the array and retain its existing elements, doing all this within O(log n). This array will later be sorted and turned into a heap, but that can be ignored, since it doesn't pertain to the problem.

The problem I am having is, one of the methods I have to implement is insert, and it must be done in O(log n). I am not given a capacity for my array. Inserting an element is easy enough, but I need to somehow accommodate for the array reaching its capacity, and still be able to insert the integer into the array without throwing an NPE. The insert method must accommodate for this without violating O(log n).

I have considered using ArrayList, where ArrayList.add is O(1), as long as the given/default length hasn't been met, otherwise it is O(n) in order to reallocate a new ArrayList with double the space, and copy the old elements into it.

Is there an implementation where you can extend an array's length and retain/copy its contents, while satisfying O(log n)?

Makoto
  • 104,088
  • 27
  • 192
  • 230
JoryAnderson
  • 103
  • 7
  • Copying each element to a new location will require `O(n)` time, and I don't see a way around this. – Tim Biegeleisen Nov 02 '16 at 02:18
  • Linked list? always O(1) if you always add element at the end or beginning? – shole Nov 02 '16 at 02:21
  • 2
    It seems to be an [X Y Problem](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) to me. Can you tell us the exact problem you are trying to solve? – Adrian Shum Nov 02 '16 at 02:23
  • 5
    `ArrayList.add` is guaranteed to be O(1) on _average_. The O(n) behavior only happens every n adds, so it averages out. Seriously, `ArrayList` is the correct `List` implementation at least 95% of the time. – Louis Wasserman Nov 02 '16 at 02:25
  • What i can guess is that you want avoid the worse case of O(n) ? for array list ? http://stackoverflow.com/questions/5846183/arraylist-vs-linkedlist – Manuel Mejias Nov 02 '16 at 02:25
  • Is your "insert" simply appending to the start/end? Or are you doing inserting to proper position so that the list remain sorted? For former case use a `LinkedList` should give you O(1) for insert. For latter case, use a `TreeSet` (assuming no duplicated elements will be given), and every insert is going to be O(log n) – Adrian Shum Nov 02 '16 at 02:47
  • @AdrianShum Sorting is to be developed later under less-strict requirements. Right now I just need to expand and retain/copy the contents of the array in O(log n) time. – JoryAnderson Nov 02 '16 at 02:57
  • then you can simply use a `LinkedList`, this give you O(1) for insert. If you want the result to be an array, you can keep inserting to the `LinkedList`, and when it is done, create an array/`ArrayList` and put the content of `LinkedList` in that array, for which will cost you O(n) but if you count towards each insert, by average it is still O(1) – Adrian Shum Nov 02 '16 at 03:00
  • And, even you are using `ArrayList`, given that each re-allocation doubles the internal size, the actual number of copies is supposed to be, in worst case, n + n/2 + n/4 + n/8 + n/16... which is `2n`. Which means, if you average that out to every insert, it is still O(1) for each insert. – Adrian Shum Nov 02 '16 at 03:07
  • @AdrianShum I appreciate your input, however the int[] array is an instance variable and the only one, and I cannot change that. I cannot maintain a linked-list and fill an empty array with its contents due to scope (I am creating a heap object that can handle inserts, deleting the minNumber and making a heap, and implementing heapSort). I am allowed to use an ArrayList instead, and I am thinking that may be the only way to do this realistically. – JoryAnderson Nov 02 '16 at 03:12
  • 1
    I don't quite understand by what way you can keep an extra `ArrayList` but not a `LinkedList`. Anyway, even you are using `ArrayList`, including the allocation overhead, it is still O(1) by **average for every insert**, which fulfill what you want. – Adrian Shum Nov 02 '16 at 03:20
  • @AdrianShum I apologize for being vague. The requirements for my assignment are to pass an `integer array` as an instance variable for a heap object I'm making. I've been told an `ArrayList` is fine though. I am in the process of trying what you and a few others have suggested. I am quite positive that what I asked in the OP is impossible. – JoryAnderson Nov 02 '16 at 03:27
  • Why not keep binary heap in given array and insert elements in it? – MBo Nov 02 '16 at 04:47

0 Answers0