Comment maintenir au mieux une liste triée à partir d'un flux d'entiers?

Question

Si j'ai un flux entrant d'entiers, comment puis-je en maintenir au mieux une liste triée? La seule façon dont je peux penser est de rechercher la position binaire et de déplacer les éléments restants vers la droite. Cela équivaudrait à $ O (n + log n) $ temps. Existe-t-il une meilleure structure de données qui peut m'aider à réaliser le même temps? Je sais que nous pouvons utiliser un arbre de recherche binaire équilibré avec $ O ( log n) $ insertions mais je voudrais avoir un accès efficace sur la liste.