Data structure

[nissanbi]

Hi,

I need to find a data structure that supports insertion, deletion and finding the median of the elements stored at the data structure.
All the operation should run in O(loglogn) amortized time.

Any ideas?
I tried using two heaps so I can find the median in O(1), but I don't thing it's good enough...

[JosAH]

@nissanbi
Google for Blum, Floyd, Rivest, Pratt and Tarjan; they've come up with an O(n) selection algorithm that finds the median in linear time. Keeping a list ordered takes O(log(n)) steps per element at worst.

kind regards,

Jos

[nissanbi]

But I don't see it helps here.

If I'm keeping the list sorted, I won't need the select algorithm. The would be found in the middle...
And even then, if each insert/delete operation would take log(n) time, I don't think that the amortized time would be log(log(n))...

[JosAH]

@nissanbi
That's what I'm saying: if you keep the list ordered you can find a median in O(1) but you have to spend O(log(n)) per element insertion/deletion.

If you don't keep the list ordered you can find a median in O(n) and you can insert/delete your elements in O(1) and O(n) respectively.

kind regards,

Jos

[nissanbi]

Lets say,
Insert- O(log(n))
Remove- O(log(n))
Find-Median- O(1)

after m1 insertion, m2 removals and m3 median findings, the amortized time would be:

((m1+m2)logn+m2) / (m1+m2+m3)
and I don't think it is equal to loglog(n)....

[JosAH]

@nissanbi
True; without knowing anything about the distribution of the numbers you can't do any better than that.

kind regards,

Jos

[nissanbi]

I also think it's impossible, but I can't find a way to prove to it's impossible...

I have another median question:

We have an AVL tree with n nodes (numbered from 1 to n).
Each node i contains a weight - wi which is an integer.
Pi is the set of the ancestors of the node i, and w(Pi) is the set of weights of all the nodes in Pi.

I need to find an algorithm which runs in O(nloglogn) time.
The algorithm gets an AVL tree like the one mentioned above and returns an array of size n, where each cell i in the array contains the median of the set W(Pi).

[JosAH]

@nissanbi
I scribbled a bit: if you sort your numbers (or keep them sorted on the fly) you need O(n*log(n)) operations (Donald Knuth, "The Art Of Computer Programming", vol III "Searching and Sorting"); you can find the median in O(1) but still it's more than O(log(log(n))); I don't know of any data structure that can do any better.

kind regards,

Jos

ps. I'll think about your other question.