python - 有效地在列表(或其他数据结构)中插入多个元素并保持它们的顺序

Question

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

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

Answer 1

这是带有大小装饰的 treap 的 python 代码，允许在特定索引处插入，并重新排序整个连续部分。它改编自 C++ 代码，Kimiyuki Onaka 对 Hackerrank 问题的解决方案，"Give Me the Order." (我不能保证这种改编没有错误——原始代码的副本可以在 this question 的描述中找到。)

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)

输出:

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
"""