2
$\begingroup$

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the right. This would amount to $O(N + \log N)$ time. Is there a better data structure that can help me achieve the same in better time? I know we can use a Balanced Binary Search Tree with $O(\log N)$ insertions but I would like to have efficient access on the list.

$\endgroup$
  • 1
    $\begingroup$ B-tree......... $\endgroup$ – Bulat Mar 11 at 14:19
  • $\begingroup$ Does it allow random access? $\endgroup$ – Andrew Scott Mar 11 at 14:24
  • 1
    $\begingroup$ Possible duplicate of Adding elements to a sorted array $\endgroup$ – xskxzr Mar 11 at 17:43
  • $\begingroup$ @AndrewScott I would like to advise you to avoid using random access to mean efficient access. You can just say "efficient access" or "fast access". Here is the conventional meaning of random access in computer science. $\endgroup$ – Apass.Jack Mar 11 at 17:57
  • $\begingroup$ Important edit - maintaining sorted list will be O(N^2). Any sort of balanced tree will be O(N*logN) $\endgroup$ – Bulat Mar 11 at 20:06
4
$\begingroup$

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.

$\endgroup$
  • $\begingroup$ @D.W. thank you. That is indeed an efficient solution. As far as the random access is concerned, I meant I only want to pick the $i$th element fairly efficiently. $\endgroup$ – Andrew Scott Mar 11 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.