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

41–50 of 76 posts

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

#41

Post by deciplex »

AYBABTME wrote: post #40
deciplex wrote: post #39

Earlier quoted context omitted.

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.

I said that:

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

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

#42

Post by [deleted] »

marvy wrote: post #4
gamesbrainiac wrote: post #3

This is a very interesting discussion, but I'd like to ask a question about this in particular: > The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative. Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assum…

You just (partially) answered your own question. Imagine something like a binary search tree. With all the pointer chasing you'll be doing, the poor pre-fetcher doesn't stand a chance.

[deleted]

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

#43

Post by skj »

abcdabcd987 wrote: post #38
wpears wrote: post #37

Earlier quoted context omitted.

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.

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.

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

#45

Post by cporios »

skj wrote: post #43
abcdabcd987 wrote: post #38

Earlier quoted context omitted.

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.

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.

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.

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

#46

Post by dubroff »

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`.

I also originally thought he had an array of arrays, but now I I think the run-times he mentioned for insertion and deletion would only work for a single array, not an array of arrays.

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

#49

Post by necessity »

blahblehbluh wrote: post #48

Some other algorithms with O(sqrt(n)) runtime: https://www.quora.com/Are-there-any-algorithms-of-the-order-...

Another one is an uniform-sized carry-select adder. It has O(sqrt(n)) delay considering MUX delay https://en.wikipedia.org/wiki/Carry-select_adder

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

#50

Post by mtdewcmu »

nikic wrote: post #13

Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the he…

Deletion can't be done efficiently, as pointed out by Timon Gehr:

>> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.

Post reply on HN