0

Short question:

Is there any data structure or algorithm that allows retrievals, insertions and deletions by index in constant time?

In detail, I want to solve the following problem (in Java):

Given a collection of positive numbers, create a data structure that allows to do the following operations granting constant time (can use up to 50-70MB):

  • Obtain the maximum or minimum element (is enough with only one) at any moment.

  • Remove and insert at a given index.

I tried to have the elements in a sorted array, and every time the top (maximum or minimum) element is deleted, mark it with a negative number then, increase an index pointing to the top element, for example:

# sortedArr[headIndex] = topElement

sortedArr = [30, 20, 9, 5, 3, 2, 1]
headIndex = 0

Delete top element (30)
sortedArr = [-1, 20, 9, 5, 3, 2, 1]
headIndex = 1

Delete top element again (20)
sortedArr = [-1, -1, 9, 5, 3, 2, 1]
headIndex = 2

The problem comes when the deleted element is not the top one, as I would lose track of the top element:

# sortedArr[headIndex] = topElement

sortedArr = [-1, -1, 9, 5, 3, 2, 1]
headIndex = 2

Delete number "3"
sortedArr = [-1, -1, 9, 5, -1, 2, 1]
headIndex = 2  # It is not updated as no top element has been removed.

Delete number "5" and "9"
sortedArr = [-1, -1, -1, -1, -1, 2, 1]
headIndex = ?

HeadIndex should be 5, but the problem is that updating headIndex, in the way that, every time there is a deletion, headIndex points to the new top element seems not possible, for that is why ask for the above data structure.

Something like double stack structure, that allowed deletions and insertions anywhere would fit me.

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
David Ivorra
  • 3
  • 2
  • I really don't see how you could claim this question is too broad. – JeremyP Nov 30 '17 at 17:35
  • I have tried to reduce it, I am new at StackOverflow, so I stil do not know how to properly post. – David Ivorra Nov 30 '17 at 17:44
  • My comment was directed at @Bohemian who I think closed it without justification – JeremyP Nov 30 '17 at 17:50
  • @JeremyP Oh, I see, thanks anyways. – David Ivorra Nov 30 '17 at 17:51
  • Practical solutions for this sort of thing use an ordered, balanced tree. By keeping child count, max in subtree, and min in subtree statistics on each node, you can do all your operations in O(log N). Red-black trees or B+ trees are popular implementations. – Matt Timmermans Dec 01 '17 at 04:33
  • @MattTimmermans I will try this approach, I only I am afraid that due to the O(log N) the solution does not completely work for me, whether or not, is worth to try. – David Ivorra Dec 01 '17 at 08:55

1 Answers1

0

BitSet comes to mind 2^31 bits would need 2^28 bytes, 256 MiB. Not requested, but iterating through it is done efficiently too.

BitSet bitSet = ...;
int max = bitSet.previousSetBit(bitSet.size() - 1);
int min = bitSet.nextSetBit(0);

The previous and next methods are inclusive.

If there are no removals, max would be calculated in O(1), whereas min unfortunately not so. As this is a form of sparse array, the general complexity of both is O(n).

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
  • I did find the size surprisingly small. Corrected – Joop Eggen Nov 30 '17 at 17:12
  • How would you find the maximum elelment in a bitset in constant time? – JeremyP Nov 30 '17 at 17:40
  • @JoopEggen Hello, thanks for the fast response, you mean using a BitSet for keeping track of which numbers have been removed? If so, does it maintain the insertion order when iterating? – David Ivorra Nov 30 '17 at 17:42
  • @DavidIvorra Simpler, as set: for a value 13: `bitset.set(13);` (add), `bitset.clear(13)` (remove), `cardinality()` (size) – Joop Eggen Nov 30 '17 at 19:04
  • @JeremyP `size()`, I hope, there is `previousSetBit(size() + 1)` otherwise – Joop Eggen Nov 30 '17 at 19:07
  • @JoopEggen Seems a very interesting approach, after I test it, I will inform whether the solution fits for me or not. – David Ivorra Dec 01 '17 at 08:52
  • [size()](https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html#size()) doesn't tell you the maximum (or minimum), it tells you how many numbers are in the `BitSet` i.e. how many of the bits are set to 1. – JeremyP Dec 01 '17 at 09:58
  • @JeremyP No `cardinality()` does that, `size()` gives `words.length * BITS_PER_WORD;` so its current capacity. Admittedly one then has to do `previousSetBit`. Not exactly the same term as Set and other collections. – Joop Eggen Dec 01 '17 at 10:05
  • Yes, you are right but my question still stands. How do you find the maximum and minimum element in constant time (which was a requirement of the question). – JeremyP Dec 01 '17 at 10:18
  • @JeremyP in that respect **BitSet fails to provide O(1)**. I should have made it a comment, but BitSet is a so underestimated class, like for setting ranges 3-42: `s.set(3, 43)`. – Joop Eggen Dec 01 '17 at 10:28
  • 1
    Thinking about it, if you record the minimum and maximum values, and adjust as necessary on insert and delete, all the operations are constant time except delete, which requires a linear search if you delete the max or min value, so even that is constant time for (n - 2)/n possible deletions. – JeremyP Dec 01 '17 at 10:41
  • @JoopEggen Thanks for properly editing the response, from that, would it be reasonable to think that if the capacity (or size) of the BitSet is forced to decrease when the top element gets removed the max operation would be always constant? – David Ivorra Dec 01 '17 at 13:36
  • JeremyP What do you concretely mean by track always the maximum and minimum values and adjust the insert and delete operations? – David Ivorra Dec 01 '17 at 13:38
  • 1
    @JeremyP Maybe I should have explained in the question that what I actually do with the collection of numbers is a serie of calls to a recursive function "f". Where I delete a number, get the maximum, call "f" with the modified collection and finally restore the collection re-inserting the number in the proper location. – David Ivorra Dec 01 '17 at 13:45
  • @DavidIvorra unfortunately `size()` indicates the actual bits capacity, and nobody would on delete shrink the array (by an array copy), as that would even be O(n). So an iteration through the words from prior max to the new max is always needed. Just try BitSet - there are not that many alternatives. – Joop Eggen Dec 02 '17 at 14:40
  • @JoopEggen Thanks, although time performance is still an issue, it seems that this is a cleaner strategy than what I had in mind. Still thinking if a data structure that solves this problem can be easily implemented. – David Ivorra Dec 04 '17 at 14:42