Re:Fast incremental sort
by larshagencpp on Sunday April 24, 2016 @12:50PM
(#11560324)
How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but maybe you mean something different.
[ Parent
| on HN ]
The items are sorted after each insertion.
Re:Fast incremental sort
by larshagencpp on Sunday April 24, 2016 @01:00PM
(#11560389)
Yes, but the incrmental sorting problem requires that the k elements are not only sorted, but are the k first elements of the whole sequence of length N.
Why does that make a difference? Every insertion into an RB tree self-balances and sorts the elements. So if you sort the first k elements (insert them in the tree), sorting the next element is fairly cheap (log k). Maybe I'm misunderstanding what you mean.