在列表（或其他数据结构）中有效插入多个元素并保持其顺序

我有一个项目列表，应该一个接一个地插入到类似列表的数据结构中，并且我有每个项目应该插入的索引。例如：

items = ['itemX', 'itemY', 'itemZ']
indexes = [0, 0, 1]

预期的结果是有一个像这样的列表：result = ['itemY', 'itemZ', 'itemX'].

我可以通过这种简单的方法得到这个结果：

result = []
for index, item in zip(indexes, items):
    result.insert(index, item)

然而，一旦列表变得巨大（复杂度为 O(n^2)），这是一种非常慢的方法。有没有（相对简单的实施）方法来改进我的基本方法？我想在插入元素并最终将该数据结构转换为我的数据结构时必须查看其他数据结构result列表。树木是一个好的选择吗？插入可能可以在 O(log(n)) （而不是 O(n)）中完成，但是我应该使用哪种特定的树状结构？

或者，也许只需将所有索引放在一起（而不是逐个使用它们）就可以实现一些好的效果。

对于我的缓慢方法来说，这可能是最糟糕的情况（始终在列表的开头插入项目）：

n = 10**6 # some large number
items = list(range(n))
indexes = [0] * n

下面是带有大小装饰的 treap 的 python 代码，允许在特定索引处插入，并对整个连续部分进行重新排序。它改编自 C++ 代码，Kimiyuki Onaka 对 Hackerrank 问题的解决方案，“给我命令。” https://www.hackerrank.com/contests/zalando-codesprint/challenges/give-me-the-order（我不能保证这个改编没有错误——原始代码的副本可以在这个问题 https://stackoverflow.com/questions/37685498/how-does-a-treap-help-to-update-this-ordered-queue.)

import random

class Treap:
  def __init__(self, value=None):
    self.value = value
    self.key = random.random()
    self.size = 1
    self.left = None
    self.right = None


def size(t):
  return t.size if t else 0


def update(t):
  if t:
    t.size = 1 + size(t.left) + size(t.right)
  return t


def merge(a, b):
  if not a:
    return b
  if not b:
    return a

  if a.key > b.key:
    a.right = merge(a.right, b)
    return update(a)
  else:
    b.left = merge(a, b.left)
    return update(b)


def split(t, i):
  if not t:
    return None, None

  if i <= size(t.left):
    u, t.left = split(t.left, i)
    return u, update(t)
  else:
    t.right, u = split(t.right, i - size(t.left) - 1)
    return update(t), u


def insert(t, i, value):
  left, right = split(t, i)
  u = Treap(value)
  return merge(merge(left, u), right)


def inorder(treap):
  if not treap:
    return

  if treap.left:
    inorder(treap.left)

  print(treap.value)

  if treap.right:
    inorder(treap.right)

Output:

lst = ['itemX', 'itemY', 'itemZ']
idxs = [0, 0, 1]

t = None

for i in range(len(lst)):
  t = insert(t, idxs[i], lst[i])

inorder(t)

"""
itemY
itemZ
itemX
"""