有效地在列表(或其他数据结构)中插入多个元素并保持它们的顺序 [英] Efficiently insert multiple elements in a list (or another data structure) keeping their order

问题描述

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

I have a list of items that should be inserted in a list-like data structure one after the other, and I have the indexes at which each item should be inserted. For example:

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

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

The expected result is to have a list like this: result = ['itemY', 'itemZ', 'itemX'].

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

I'm able to get this result with this simple approach:

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

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

However, this is a very slow approach once lists become huge (the complexity is O(n^2)). Is there any (relatively simple to implement) way to improve my basic approach? I guess I have to look at other data structures while I insert elements and finally transform that data structure into my result list. Are trees a good option? Insert could be done maybe in O(log(n)) (instead of O(n)), but which specific tree-like structure should I use?

或者也许可以通过一起查看所有索引(而不是一个一个地使用它们)来实现一些好的东西.

Or maybe something good can be achieved by just looking at all the indexes together (instead of using them one by one).

这可能是我的缓慢方法的最坏情况(总是在列表的开头插入项目):

This is probably the worst case for my slow approach (always insert items at the beginning of the list):

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

推荐答案

这里是带有大小修饰的 treap 的 python 代码，允许在特定索引处插入，并重新排序整个连续部分.它改编自 C++ 代码，Kimiyuki Onaka 对 Hackerrank 问题的解决方案，给我订单".(我不能保证这种改编没有错误——原始代码的副本可在 这个问题.)

Here's python code for a treap with a size decoration that allows insertion at specific indexes, and reordering of whole contiguous sections. It was adapted from C++ code, Kimiyuki Onaka's solution to the Hackerrank problem, "Give Me the Order." (I cannot guarantee that this adaptation is bug free -- a copy of the original code is available in the description of 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
"""

这篇关于有效地在列表(或其他数据结构)中插入多个元素并保持它们的顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！