On 12/01/2015 04:50 AM, Emil Kirschner wrote:
> On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
>> Okasaki's book is a continued inspiration of data structures and
>> algorithms.
>> Start with a simple array of data. Then mentally decompose that array
>> into a concatenation of smaller arrays: first has size 1, second has
>> size 4, third has size 9, then 16, 25, 36, ... Generally the size of
>> these imaginary subarrays grows quadratically. And they're adjacent to
>> each other. The last array may be incomplete.
>> ........
>> Please share any thoughts!
>>
>>
>> Andrei
>
> Interesting, but isn't that basically a skip list with uneven sub-lists?
> insert could be quite complex unless the entire data structure is backed
> by a continuous or a continuous linked list.

Doesn't look like a skip list to me. -- Andrei

On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
> On 11/30/15 9:47 PM, Timon Gehr wrote:
>> On 12/01/2015 03:33 AM, Timon Gehr wrote:
>>> On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
>>>> So now consider my square heaps. We have O(n) build time (just a bunch
>>>> of heapifications) and O(sqrt n) search.
>>>
>>> How do you build in O(n)? (The initial array is assumed to be completely
>>> unordered, afaict.)
>>
>> (I meant to say: There aren't any assumptions on the initial ordering of
>> the array elements.)
>
> That's quite challenging. (My O(n) estimate was off the cuff and
> possibly wrong.) Creating the structure entails simultaneously solving
> the selection problem (find the k smallest elements) for several values
> of k. I'll post here if I come up with something. -- Andrei

OK, I think I have an answer to this in the form of an efficient algorithm.

First off: sizes 1+3+5+7+... seem a great choice, I'll use that for the initial implementation (thanks Titus!).

Second: the whole max heap is a red herring - min heap is just as good, and in fact better. When doing the search just overshoot by one then go back one heap to the left and do the final linear search in there.

So the structure we're looking at is an array of adjacent min-heaps of sizes 1, 3, 5, etc. The heaps are ordered (the maximum of heap k is less than or equal to the minimum of heap k+1). Question is how do we build such an array of heaps in place starting from an unstructured array of size n.

One simple approach is to just sort the array in O(n log n). This satisfies all properties - all adjacent subsequences are obviously ordered, and any subsequence has the min heap property. As an engineering approach we may as well stop here - sorting is a widely studied and well implemented algorithm. However, we hope to get away with less work because we don't quite need full sorting.

Here's the intuition: the collection of heaps can be seen as one large heap that has a DAG structure (as opposed to a tree). In the DAG, the root of heap k+1 is the child of all leaves of heap k (see http://imgur.com/I366GYS which shows the DAG for the 1, 3, 7, and 7 heaps).

Clearly getting this structure to respect the heap property is all that's needed for everything to work - so we simply apply the classic heapify algorithm to it. It seems it can be applied almost unchanged - starting from the end, sift each element down the DAG.

This looks efficient and minimal; I doubt there's any redundant work. However, getting bounds for complexity of this will be tricky. Classic heapify is tricky, too - it seems to have complexity O(n log n) but in fact has complexity O(n) - see nice discussion at http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity. When applying heapify to the DAG, there's more restrictions and the paths are longer, so a sliver more than O(n) is expected.

Anyway, this looks ready for a preliminary implementation and some more serious calculations.

One more interesting thing: the heap heads are sorted, so when searching, the heap corresponding to the searched item can be found using binary search. That makes that part of the search essentially negligible - the lion's share will be the linear search on the last mile. In turn, that suggests that more heaps that are smaller would be a better choice. (At an extreme, if we have an array of heaps each proportional to log(n), then we get search time O(log n) even though the array is not entirely sorted.)


Andrei

On Tuesday, 1 December 2015 at 22:48:56 UTC, Andrei Alexandrescu wrote:
> On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
>> On 11/30/15 9:47 PM, Timon Gehr wrote:
>>> On 12/01/2015 03:33 AM, Timon Gehr wrote:
>>>> On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
>>>>> So now consider my square heaps. We have O(n) build time (just a bunch
>>>>> of heapifications) and O(sqrt n) search.
>>>>
>>>> How do you build in O(n)? (The initial array is assumed to be completely
>>>> unordered, afaict.)
>>>
>>> (I meant to say: There aren't any assumptions on the initial ordering of
>>> the array elements.)
>>
>> That's quite challenging. (My O(n) estimate was off the cuff and
>> possibly wrong.) Creating the structure entails simultaneously solving
>> the selection problem (find the k smallest elements) for several values
>> of k. I'll post here if I come up with something. -- Andrei
>
> OK, I think I have an answer to this in the form of an efficient algorithm.
>
> First off: sizes 1+3+5+7+... seem a great choice, I'll use that for the initial implementation (thanks Titus!).
>
> Second: the whole max heap is a red herring - min heap is just as good, and in fact better. When doing the search just overshoot by one then go back one heap to the left and do the final linear search in there.
>
> So the structure we're looking at is an array of adjacent min-heaps of sizes 1, 3, 5, etc. The heaps are ordered (the maximum of heap k is less than or equal to the minimum of heap k+1). Question is how do we build such an array of heaps in place starting from an unstructured array of size n.
>
> One simple approach is to just sort the array in O(n log n). This satisfies all properties - all adjacent subsequences are obviously ordered, and any subsequence has the min heap property. As an engineering approach we may as well stop here - sorting is a widely studied and well implemented algorithm. However, we hope to get away with less work because we don't quite need full sorting.
>
> Here's the intuition: the collection of heaps can be seen as one large heap that has a DAG structure (as opposed to a tree). In the DAG, the root of heap k+1 is the child of all leaves of heap k (see http://imgur.com/I366GYS which shows the DAG for the 1, 3, 7, and 7 heaps).
>
> Clearly getting this structure to respect the heap property is all that's needed for everything to work - so we simply apply the classic heapify algorithm to it. It seems it can be applied almost unchanged - starting from the end, sift each element down the DAG.
>
> This looks efficient and minimal; I doubt there's any redundant work. However, getting bounds for complexity of this will be tricky. Classic heapify is tricky, too - it seems to have complexity O(n log n) but in fact has complexity O(n) - see nice discussion at http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity. When applying heapify to the DAG, there's more restrictions and the paths are longer, so a sliver more than O(n) is expected.
>
> Anyway, this looks ready for a preliminary implementation and some more serious calculations.
>
> One more interesting thing: the heap heads are sorted, so when searching, the heap corresponding to the searched item can be found using binary search. That makes that part of the search essentially negligible - the lion's share will be the linear search on the last mile. In turn, that suggests that more heaps that are smaller would be a better choice. (At an extreme, if we have an array of heaps each proportional to log(n), then we get search time O(log n) even though the array is not entirely sorted.)
>
>
> Andrei

Nice to see this interesting post and learn.

 I have a few questions.

1) This is offline datastructure since you don't know how the elements of the future are going to be ie dynamic. ie later elements from n to 2n can break or change your heaps as such in worst case or is it a dynamic data structure ?

2)  Searching in min or max heaps is bad isn't it ? Lets say we choose max heaps. Now we have the root as 10^9 in the second last heap ie around n^2 elements.  The children of it are 4*10^8 and 5*10^8 . If i'm searching for say 4.5 *10^8 my job is easy but if i'm searching for 1000, i have to search in both the subtrees and it goes linear and becomes around n^2 in the worst case. Did i overlook anything ?

Instead of heaps, a single sorted array or breaking them into a series of sorted arrays ie skip lists kind of stuff  would be fine if it just want a offline Data structure ?

or is this some domain specific data Structure where you only/cre want max/min in some sequence ?

On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
> Okasaki's book is a continued inspiration of data structures and algorithms.
>
> [...]

Sort of reminds me of a modified Hashed Array Tree — not keen on the name, I think "Bucket Array" would have been better.
https://en.wikipedia.org/wiki/Hashed_array_tree

On 12/01/2015 11:48 PM, Andrei Alexandrescu wrote:
> On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
>> On 11/30/15 9:47 PM, Timon Gehr wrote:
>>> On 12/01/2015 03:33 AM, Timon Gehr wrote:
>>>> On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
>>>>> So now consider my square heaps. We have O(n) build time (just a bunch
>>>>> of heapifications) and O(sqrt n) search.
>>>>
>>>> How do you build in O(n)? (The initial array is assumed to be
>>>> completely
>>>> unordered, afaict.)
>>>
>>> (I meant to say: There aren't any assumptions on the initial ordering of
>>> the array elements.)
>>
>> That's quite challenging. (My O(n) estimate was off the cuff and
>> possibly wrong.) Creating the structure entails simultaneously solving
>> the selection problem (find the k smallest elements) for several values
>> of k. I'll post here if I come up with something. -- Andrei
>
> OK, I think I have an answer to this in the form of an efficient algorithm.
>
> First off: sizes 1+3+5+7+... seem a great choice, I'll use that for the
> initial implementation (thanks Titus!).
>
> Second: the whole max heap is a red herring - min heap is just as good,
> and in fact better. When doing the search just overshoot by one then go
> back one heap to the left and do the final linear search in there.
>
> So the structure we're looking at is an array of adjacent min-heaps of
> sizes 1, 3, 5, etc. The heaps are ordered (the maximum of heap k is less
> than or equal to the minimum of heap k+1). Question is how do we build
> such an array of heaps in place starting from an unstructured array of
> size n.
>
> One simple approach is to just sort the array in O(n log n). This
> satisfies all properties - all adjacent subsequences are obviously
> ordered, and any subsequence has the min heap property. As an
> engineering approach we may as well stop here - sorting is a widely
> studied and well implemented algorithm. However, we hope to get away
> with less work because we don't quite need full sorting.
>
> Here's the intuition: the collection of heaps can be seen as one large
> heap that has a DAG structure (as opposed to a tree). In the DAG, the
> root of heap k+1 is the child of all leaves of heap k (see
> http://imgur.com/I366GYS which shows the DAG for the 1, 3, 7, and 7 heaps).
>
> Clearly getting this structure to respect the heap property is all
> that's needed for everything to work - so we simply apply the classic
> heapify algorithm to it. It seems it can be applied almost unchanged -
> starting from the end, sift each element down the DAG.
>
> This looks efficient and minimal; I doubt there's any redundant work.
> However, getting bounds for complexity of this will be tricky. Classic
> heapify is tricky, too - it seems to have complexity O(n log n) but in
> fact has complexity O(n) - see nice discussion at
> http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity.
> When applying heapify to the DAG, there's more restrictions and the
> paths are longer, so a sliver more than O(n) is expected.
>
> Anyway, this looks ready for a preliminary implementation and some more
> serious calculations.
>

Assume the initial array is sorted from largest to smallest. This will be the worst case for this construction algorithm, as each element will be sifted all the way down to leaf level of the last heap.

For simplicity, let's assume that n = m² for m odd, such that the sizes of the heaps are 1,3,…,m. To sift some element down one entire heap of size i takes ≥ log₂(i) steps.

Ignoring the work performed in the heaps each elements starts in (which is obviously at most O(n) in total), we can lower bound the performed work; for the heap of size j, we sift j elements down all the following heaps of sizes i=j+1,i=j+2,…,i=m:

∑ⱼ[j∈{1,3,…,m}]·j·∑ᵢ[j+1≤i≤m]·log(i)
=
∑ᵢ∑ⱼ[j∈{1,3,…,m}]·[j+1≤i≤m]·j·log(i)
=
∑ᵢ[2≤i≤m]·log(i)·∑ⱼ[j∈{1,3,…,m}]·[j+1≤i] j
=
∑ᵢ[2≤i≤m]·log(i)·∑ⱼ∑ₖ[j=2·k+1]·[1≤j≤m]·[j≤i-1] j
=
∑ᵢ[2≤i≤m]·log(i)·∑ⱼ∑ₖ[j=2·k+1]·[1≤2·k+1≤i-1]·(2·k+1)
=
∑ᵢ[2≤i≤m]·log(i)·∑ₖ[1≤2·k+1≤i-1]·(2·k+1)
=
∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
=
∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
≥
Ω(m³)
=
Ω(n^(3/2)).

I.e. sorting is asymptotically faster, and probably also in practice. Moreover, the construction algorithm would be slower even if sifting down one entire heap would run in constant time.

However, for your adapted data structure with min-heaps, implementing insert and remove in O(√n̅ log n) is now easy using your "sifting in a DAG" approach.

One way to prove a useful lower bound on the time it must take to build might be to observe that building recursively can be used for sorting.

> One more interesting thing: the heap heads are sorted, so when
> searching, the heap corresponding to the searched item can be found
> using binary search. That makes that part of the search essentially
> negligible - the lion's share will be the linear search on the last
> mile. In turn, that suggests that more heaps that are smaller would be a
> better choice. (At an extreme, if we have an array of heaps each
> proportional to log(n), then we get search time O(log n) even though the
> array is not entirely sorted.)
>
>
> Andrei
>

The linear search can have way better locality, so it is likely that actually the binary search dominates for some data sets.

On 12/02/2015 12:26 PM, Timon Gehr wrote:
> ...
> ∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
> =
> ∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
>

It should actually be (⌊i/2⌋-1)² here, but this does not change the asymptotics.

On 12/02/2015 03:29 PM, Timon Gehr wrote:
> On 12/02/2015 12:26 PM, Timon Gehr wrote:
>> ...
>> ∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
>> =
>> ∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
>>
>
> It should actually be (⌊i/2⌋-1)² here, but this does not change the
> asymptotics.

Oops. No, it was actually right. Sorry for the noise. :-)

On 12/02/2015 06:26 AM, Timon Gehr wrote:
> The linear search can have way better locality, so it is likely that
> actually the binary search dominates for some data sets.

Galloping search ftw (good locality, log complexity). -- Andrei

On Wed, 02 Dec 2015 05:58:24 +0000, Navin wrote:

> Nice to see this interesting post and learn.
> 
>   I have a few questions.
> 
> 1) This is offline datastructure since you don't know how the elements of the future are going to be ie dynamic. ie later elements from n to 2n can break or change your heaps as such in worst case or is it a dynamic data structure ?

You can usually change an offline datastructure into an amortized online one. (I think.) You can usually change an amortized online algorithm into a deamortized one with a series of ugly hacks and large increases in constants.

I think you can make insertions work and not be too terrible with an amortized algorithm. Something like:

To insert a value X into the square heap, find the largest heap with a head equal to X. If there is none, find the smallest heap with a head greater than X. If there is none, choose the final heap. If that heap is not full, insert X into it. If it is full, trigger a rebalance.

'Rebalance' is an operation we use to ensure that each intermediate heap is exactly half full (rounding down) and the final heap is no more than half full. We start at a given heap. We calculate its surplus -- the number of elements it has in excess of half its capacity. We scan to the right (increasing heap sizes) until we find a heap with at least enough spare capacity to hold the surpluses of all the prior heaps we've scanned. If we reach the end of the square, we create a new heap. This is the target heap.

Now we repeatedly bubble up values from lower heaps to higher ones until no heap between the one we tried to insert into and the target heap has any surplus.

This costs us in the worst case something like O(n * log(n) * sqrt(n)). I haven't done the full analysis. But after doing a large rebalance, you shouldn't need to do a large rebalance for quite a while, so the average case, even on adversarial data, should be not so horrible.

Deletions are simple: find the element and remove it from its heap. This can, however, reduce a heap to less than half filled. (This means I can insert and delete elements in an adversarial pattern to force all elements into one heap.) A similar rebalance algorithm is needed, but it's harder on this side because we're using max heaps everywhere and need to fill lower heaps.

> 2)  Searching in min or max heaps is bad isn't it ?

Linear time in the worst case. If you're looking for something in a max heap that happens to be the smallest element, it can be in any leaf node, which gives you half the tree to look through. And the average isn't much better.

However, if we can guarantee that an element is in one heap inside this square heap, it costs us O(sqrt n) to search that heap since that heap has no more than sqrt(n) elements.

> Lets say we choose
> max heaps. Now we have the root as 10^9 in the second last heap ie
> around n^2 elements.  The children of it are 4*10^8 and 5*10^8 . If i'm
> searching for say 4.5 *10^8 my job is easy but if i'm searching for
> 1000, i have to search in both the subtrees and it goes linear and
> becomes around n^2 in the worst case. Did i overlook anything ?
> 
> Instead of heaps, a single sorted array or breaking them into a series of sorted arrays ie skip lists kind of stuff  would be fine if it just want a offline Data structure ?

A skiplist is great. Problem is, it's random access to memory. That's bad enough at the best of times, and it's utter garbage if you're storing data on spinning disks. Even if you store it as a sorted list rather than a linked list, which means you never insert anything ever, it's O(log n/ B) seeks and reads to find an element. If you store it as a linked list, it's O(log n) reads.

A square heap with an insertion algorithm as I describe gives you O(1) seeks and O(sqrt n/B) reads.

(Here, B stands for block size, which in this case is the number of data elements you will naturally get for free or almost for free after reading one byte. When I was doing data structure research, the rule of thumb was that a block is roughly 1MB for spinning disks. Divide that by element size to get B.

We track seeks separately because they're expensive. 9ms is a reasonable seek time. Comparatively, reading data sequentially is extremely cheap, especially if you can inform the disk scheduler that you are going to perform sequential reads. Seeks are expensive no matter what, even if you can inform the scheduler in advance -- and the skiplist doesn't let you do that.

Even if you switch to SSDs, SSDs tend to be ~4x faster on sequential reads than random reads.)

So if you have 64-byte data structures, for instance, and you've got a billion on disk, you have sixteen seeks for a skiplist on average, which costs you 144ms. (You can drop that a bit by keeping the top of the skiplist in memory.)

The square heap, on the other hand? You've got a total of ~1500 heaps, so you can store their offsets and heads in memory. That means you identify the heap containing the element you're searching for without touching disk, and scanning the heap costs one seek and a scan. You're scanning 700K elements on average, which means you need to look through forty or so blocks.

So the square heap could well be more efficient here. It costs ~3x the number of reads, but they're all sequential, so while it's close, the square heap probably wins out on average.

But this isn't yet a viable real-world algorithm for most things because of amortized inserts that promise to be expensive even after they're deamortized. And I haven't even sketched out an algorithm for deletes.

At least range queries will typically be reasonably fast.

> or is this some domain specific data Structure where you only/cre want max/min in some sequence ?

On 12/02/2015 06:26 AM, Timon Gehr wrote:
> Assume the initial array is sorted from largest to smallest. This will
> be the worst case for this construction algorithm, as each element will
> be sifted all the way down to leaf level of the last heap.
[...]
> Ω(n^(3/2)).

Thanks. My math-fu is not good enough to properly follow the argument, but that bound sounds high; one intuition is that there shouldn't be more work done than in sorting - fewer swaps, fewer comparisons, less resulting structure.

For example, heapifying the array 1, 2, 3, 4, 5, 6, 7, 8, 9 in 1+3+5 max heaps results in the array 9, 8, 6, 7, 5, 4, 3, 2, 1 which is "less sorted" than the fully sorted array. (I know, that doesn't prove anything.)

At this point I need to either get to the bottom of the math or put together an experimental rig that counts comparisons and swaps.

(BTW I figured one reason for which these DAG heaps work at all is that there's never a need to sift an element up between heaps; that would be inefficient because the root of a subheap has multiple parents. Sifting down is efficient because each node has at most two children.)


Andrei