3 ms·
The items are sorted after each insertion.
by Scea91 11y ago
The items are sorted after each insertion.
- larshagencpp 11y agoYes, 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.
- cyphar 11y agoWhy 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.