On 12/03/2015 11:44 PM, Andrei Alexandrescu wrote:
> 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,

There was actually an (asymptotically inconsequential) error in the initial expression. Fixed version:

Ignoring the work performed in the heaps each elements starts in (which is obviously at most O(n)), 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+2,i=j+4,…,i=m).


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



Less formally:

The heap of size 3 is sifted through by 1=1² element from the first heap.
The heap of size 5 is sifted through by 1+3=2² elements from the first and second heaps
The heap of size 7 is sifted through by 1+3+5=3² elements from the first three heaps.
...
The heap of size 2·k+1 is sifted through by k² elements.
...
The heap of size m is sifted through by ((m-1)/2)² elements.

This gives the last sum in the above derivation:

     sifting through heap of size 2·k+1 costs at least log(2·k+1)
                                v
        ∑ₖ[1≤k≤(m-1)/2]·log(2·k+1)·k²
             ^
k ranges from 1 to (m-1)/2.

The factor k² is the number of elements sifting through the heap of size 2·k+1.

The sum can be lower bounded by
1+2²+3²+…+((m-1)/2)²
=
(m+1)·(m-1)·(m-3)/24+(m+1)·(m-1)/8
=
(m³-m)/24
≥
Ω(m³).


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

That intuition is spot on, but the sorting algorithm that the construction algorithm imitates most closely is a version of insertion sort.

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

It provides motivation to try and find another construction algorithm that runs asymptotically faster than n log n, or to prove that n log n is asymptotically optimal.

> At this point I need to either get to the bottom of the math or

The basic argument is not too involved: If each element needs to be sifted all the way down to the last heap, then for each of √n̅ heaps, you need to sift all its ~√n̅ elements down ~√n̅ other heaps, which requires more than ≈n^(3/2) operations. The above derivation makes this rigorous.

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

Good point. I had declared victory on the "insert" front too early.

Hello all!  I happened by this thread (from Hacker News) and the idea of this data structure got stuck in my head.  I did some scribbling on paper and decided that it could be interesting to code...

On Thursday, 3 December 2015 at 22:44:26 UTC, Andrei Alexandrescu wrote:
> 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.

I've built a test implementation (in C++ ... I hope that isn't too distasteful on a D forum, but it's what I'm most comfortable with) here:  https://github.com/jcausey-astate/HeapArray

I chose to use a Min-Max heap[1] for the heaps themselves (this buys me O(1) min and max access).  This solves the problem of making insert and delete follow the same pattern (to insert, ripple the max value in a full partition to the next one; in a delete, fill in the "hole" with min value from previous partition).

I wasn't able to come up with anything better than pre-sorting the whole thing, then running the Floyd "make heap" on each partition.  So, the whole thing costs O(n*lg(n) + n)) to make a new structure on top of an existing array.  This is still faster than doing a top-down (add every element) make-heap though.  I agree with Timon's analysis[2] on that.

I also agree with Andrei that I have a "gut feeling" that there could be a faster setup algorithm, since we really just need to shuffle values into the right partitions, not actually fully sort them... But that would require knowing exactly what the partition "pivot" values were in advance, which would require searching, and 'round we go.

My code is still rough, only works for ints, and needs some documentation and cleanup, but it does show that our hunches were more or less correct:  This thing is much faster than linear for searching, but not as fast as logarithmic.  It also performs OK when adding new values and performing lots of searches (when compared with a plain old array or vector where you have to linear search every time).


My Github README has some charts, but I'll link a couple here:
Search times (vector VS this structure VS multiset)
https://plot.ly/~jcausey-astate/7/search-timing-vector-vs-heaparray-vs-multiset/

Time to add N values starting with an empty structure (vector VS this structure VS multiset)
https://plot.ly/~jcausey-astate/18/fill-container-dynamically-heaparray-vs-vector-and-multiset/

Time to initially build the structure given an already-populated array (vector VS this structure VS multiset):
https://plot.ly/~jcausey-astate/35/build-data-structure-on-existing-array-all-at-once/


[1]: http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02../Atkinson86.pdf

[2]: http://forum.dlang.org/post/n3qqkm$2c6t$1@digitalmars.com