Finding a small element in a changing array

Question

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like.

The array is initialized to zeros.

The goal to to support two operations:

• Update(k,v) - sets $A[k]=v$.
• Small() - returns an index in which the element is smaller than or equal to the median.

Assuming that finding a small item has to be done in $O(1)$ time, how fast can we perform updates?

Some notes:

• You can use preprocessing to initialize any data structure you wish before the sequence of updates starts.

• I'm only looking for deterministic algorithms. A randomized algorithm for this problem is trivial.

• Making update run in $O(\log n)$ is straightforward (e.g. using a balanced BST).

Can we improve to $o(\log n)$ or show an $\Omega(\log n)$ lower bound?

Answer 1

Here is an amortized solution to the problem in which updates may only increase values:

Maintain:

1. A linked list of some of the items less than the median

2. A linked list of all items greater than the median (and some items less than it)

To return a small item, return an item from #1.

To update an item greater than the median, change its key in #2.

To update an item less than the median, remove it from #1 and add it to #2. If this makes #1 empty, rebuild both lists using a linear-time partitioning algorithm.

Update takes amortized constant time, using physicists argument and a potential function of twice the size of list #2 or the bankers argument and two coins on each item in list #2.

Here is an amortized solution in which updates may increase or decrease values:

To start, build three linked lists of size $n/3$. All items in list #1 should be less than all items in list #2, and all items in list #2 should be less than all items in list #3. One more list will be maintained; I'll call it the junkyard.

To change the key of an item:

• When increasing the key of an item in #1, move it to the junkyard.

• When decreasing the key of an item in #3, move it to the junkyard.

• When changing the key of an item from #2, move it to the junkyard.

• When changing any other key, do not remove it from or add it to any list.

The junkyard is called "full" when it has size $n/6$. Until then, all items in #1 are less than the median. Once the junkyard is full, rebuild.

The amortization argument works the same, but now the potential is six times the size of the junkyard, or, equivalently, each move to the junkyard requires 6 coins.

Here is a complete deamortized solution:

All operations can be done in constant time using a technique called incremental global rebuilding.

Maintain three copies of the second version of the structure designed above, along with three pointers to them, called PAST, PRESENT, and FUTURE. If a structure is pointed to by A and we want to point to it from B, we call that "renaming A to B".

We will proceed in four stages. After stage 4, we will rename PRESENT to PAST, rename FUTURE to PRESENT, and point the FUTURE pointer at empty space (or the null pointer). Then we will start with stage 1 all over again.

Each stage lasts $n/36$ updates. Queries are always answered from PRESENT

Stage 1:

When this stage starts:

• We will never query the structure pointed to by PAST again. It is dead, so we don't really care about its contents.

• PRESENT's junkyard has at most $2n/36$ items in it.

• FUTURE is just a null pointer.

During this stage, updates are performed on PRESENT as usual, but for each update, we perform 36 steps of destructing PAST. As a result, by the end of this stage, $n$ destructing steps have been performed on PAST and it is empty, using no memory.

At the end of this stage, PRESENT's junkyard might be as large as $3n/36$.

Stage 2:

When this stage starts, we allocate an empty linked list that we call FUTURE.

During this stage, for each update to PRESENT we also copy 36 items into FUTURE. Also, for each item that is updated, we update its key in FUTURE if it already has been copied. Note that the update in FUTURE doesn't touch any junkyards, since FUTURE is just a linked list at this point.

At the end of this stage, PRESENT's junkyard might be as large as $4n/36$, and the items in PRESENT and FUTURE are identical.

Stage 3:

When this stage starts, we allocate an empty queue that can hold representations of update operations (for instance, as a pair containing a pointer to the item and its new value).

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue, and we perform 36 steps of the initialization of FUTURE into the structure described in section 2 above. As a result, by the end of this stage, $n$ initialization steps have been performed on FUTURE and it is completely initialized, with a junkyard size of 0. However, because updates were queued, it does not hold the same data as PRESENT, which we will have to fix in Stage 4.

At the end of this stage, PRESENT's junkyard might be as large as $5n/36$ and the queue has size $n/36$.

Stage 4:

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue and dequeue two operations to play back in FUTURE. During this stage the queue grows by $n/36$ operations and shrinks by $2n/36$, leaving it empty at the end of the stage.

At the end of this stage, PRESENT's junkyard might be as large as $6n/36$ and FUTURE's junkyard might be as large as $2n/36$. We now switch names as described above, renaming PRESENT to PAST, FUTURE to PRESENT, and pointing FUTURE at the null pointer. The prerequisites for Stage 1 are now met, and at no point did PRESENT have more than $n/6$ items in its junkyard.