Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An interesting data structure with search time O(sqrt n)

forum.dlang.org

Post reply on HN
Print view View original

31–40 of 76 posts

Re: An interesting data structure with search time O(sqrt n)

#31

Post by 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!

Re: An interesting data structure with search time O(sqrt n)

#32

Post by JBiserkov »

rntz wrote: post #14
chias wrote: post #12

Isn't O(log(n)) equivalent to O(sqrt(n))?

No. Just as (e^n) grows faster (in the limit) than any polynomial of n, such as n^2 or n^100; likewise, log(n) grows slower than any polynomial of n, such as sqrt(n) = n^(1/2), or even n^(1/100). They are both practically pretty slow-growing, though. It may well be that for practical sizes, constant factors matter more than the asymptotic difference on present computers.

In Parallel programming class the professor told us: "When I was a student, our professor told us that for practical purposes log(n) = 7"

Re: An interesting data structure with search time O(sqrt n)

#33

Post by mden »

DannyBee wrote: post #29
drfuchs wrote: post #16

Earlier quoted context omitted.

No, because sqrt(n)/log(n) is not bounded by a constant as n approaches infinity. Consider: in base 10, if log(n)=10, then sqrt(n) is 5 digits; if log(n)=100, then sqrt(n) is 50 digits; if log(n)=1000, then sqrt(n) is 500 digits; etc.

Errr, what? natural log grows slower than sqrt(n) http://www.wolframalpha.com/input/?i=sqrt%281e55%29+%3E+log%...

I think that's the point he is making as well. Except it might be confusing that he is using numbers for log(n) and number of digits for srqt(n).

Re: An interesting data structure with search time O(sqrt n)

#35

Post by sethammons »

bpicolo wrote: post #23
mmozeiko wrote: post #22

Earlier quoted context omitted.

I won't be array of arrays. It will be just one array.

we decompose an array of size 35 into: an array of size 1 followed by arrays of sizes 4, 9, 16, 5 Then again, maybe he means `mentally decompose` in terms of pretending they're separate arrays? I interpreted it as `visualize this data structure`.

That is the way I took it too

Re: An interesting data structure with search time O(sqrt n)

#36

Post by deciplex »

rntz wrote: post #17

I don't understand this bit: > Now each of these arrays we organize as a max heap. Moreover, we arrange data such that the maximums of these heaps are in INCREASING order. That means the smallest element of the entire (initial) array is at the first position, then followed by the next 4 smallest organized in a max heap, Just because the maximums of the heaps are increasing order doesn't mean that the minimum is at th…

I'm pretty sure there is an additional (unstated) assumption that each element of each subarray is less than all elements of subsequent subarrays. Otherwise you could just take the largest sqrt(n) elements, sort them, and then randomly assign the other elements of the collection to their heaps and it would still meet the criteria he's laid out, but the search algorithm he's proposed wouldn't work.

In fact, there's an error in the search algorithm as well:

> Whenever the maximum element (first element in the subarray) is smaller than the searched value, we skip over that entire heap and go to the next one. In the worst case we'll skip O(sqrt n) heaps. When the max value in a heap is less than the searched element, we found the heap and we run a linear search among O(sqrt n) elements.

For the unitalicized portion above, he means to say "When the max value in a heap is greater than the searched element".

Re: An interesting data structure with search time O(sqrt n)

#37

Post by wpears »

abcdabcd987 wrote: post #31

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^…

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

Re: An interesting data structure with search time O(sqrt n)

#38

Post by abcdabcd987 »

wpears wrote: post #37
abcdabcd987 wrote: post #31

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^…

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

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.

Re: An interesting data structure with search time O(sqrt n)

#39

Post by deciplex »

abcdabcd987 wrote: post #31

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^…

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.

Re: An interesting data structure with search time O(sqrt n)

#40

Post by AYBABTME »

deciplex wrote: post #39
abcdabcd987 wrote: post #31

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^…

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'…

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.
Post reply on HN