[abcdabcd987]

I'm confused. I can follow the logic for O(sqrt n) searching. yeah, that's cool. But how to maintain the structure when inserting or deleting?

Insertion for example, if I want to insert a value which is smaller than the smallest element in the last heap, then it'll have to be inserted into some heap in the middle, right? And since the heap is in the middle, say heap K, its size already reaches its upper limitation K^2. Then where should the new value go? If I insist on pushing it into heap K, then the heap will violate the size limitation. Should I split the oversized heap into several heaps some time? If it does split, will the O(sqrt n) searching time still holds?

Or maybe I just have not caught the author's idea yet. :-(

BTW, why not BST, for everything is O(log n)?

Update: @nikic solved my questions. Thanks!

[deciplex]

I think for insertion, once you find the heap the new element should be inserted into, you would remove the max element from the heap, and re-heapify that subarray with the new element. Then you would insert the max you just removed into the next heap in the same way, and so on. That sounds like it could be less expensive than shifting the whole array, but I haven't done the math (and it seems that Alexandrescu hasn't either, yet).

Note that I'm making a couple assumptions about the data structure that were left unstated in the original post:

* Each element of each heap is less than every element of every subsequent heap.

* "When the max value in a heap is less than the searched element" was a typo and "When the max value in a heap is greater than the searched element" was intended.

Maybe I just totally misunderstand this data structure though :-( It's still morning for me.

[AYBABTME]

You'd re-heapify all heaps greater than the one that ejected an element, since heaps greater than you are all full except for the very last one.

[deciplex]

I said that:

> Then you would insert the max you just removed into the next heap in the same way, and so on.

[wpears]

BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)

[abcdabcd987]

Well, it's not a big problem. This case won't exist in most BSTs. Even if it appears in some BST, splay tree for example, it will be amortized.

[skj]

I'm not really sure what amortization you're talking about here.

BSTs are O(n) lookup, and the pathological case is quite easy to achieve: add elements to it in sorted order.

There are other trees that have O(lg n) lookup. Red-black trees are the canonical example.

[cporios]

BSTs can have O(lg n) lookups. A Red-black tree is such an example. It is a self-balancing BST, so a red-black tree is a BST itself.

[hvidgaard]

And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.

[Veedrac]

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.