如何高效地将元素插入已排序的向量？

Question

我是一名有用的助手，可以翻译文本。

我有一个已排序的v: Vec<EventHandler<T>>，我想在保持排序的同时将一个元素插入其中。最有效的方法是什么？Rust似乎没有内置的方法来实现这一点。 EventHandler<T>如下：

struct EventHandler<T: Event + ?Sized> {
    priority: i32,
    f: fn(&mut T),
}

由于排序的工作方式，插入和排序将效率低下，时间复杂度为O(n log n)，分配成本为2*n。请参考Vec::sort_by。

- SoniEx2

---

Vec 已经实现了 binary_search 和 insert 方法。因此只需要找到合适的索引并在那里插入新元素即可。 - Konstantin V. Salikhov

这个问题为什么不好？ - SoniEx2

@SoniEx2 我不确定为什么人们会对此进行负评，但请添加一些代码。这将命名某些变量 - 答案可以轻松地引用这些名称。您还可以问“最好的[或最短的]方法是什么...”。 - Lukas Kalbertodt

这个问题等同于“如何用螺丝刀高效地钉钉子？”将元素插入到向量中间需要将后续所有项下移，这将始终是O(n)的操作。使用维护排序性质的数据结构。BinaryHeap 是一个可能的选择。 - Shepmaster

关于在向量中插入多个项的相关问题（https://dev59.com/EV4b5IYBdhLWcg3wzUYp） - Shepmaster

Answer 1

这项任务分为两个步骤：使用binary_search找到插入位置，再使用Vec::insert()进行插入：

match v.binary_search(&new_elem) {
    Ok(pos) => {} // element already in vector @ `pos` 
    Err(pos) => v.insert(pos, new_elem),
}

如果您想在向量中允许重复元素，因此希望插入已经存在的元素，则可以写得更简短：

let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e);
v.insert(pos, new_elem);

---

但是，请注意这具有 O(n) 的运行时间复杂度。要在中间插入元素，向量必须将插入位置右侧的每个元素向右移动一位。

因此，您不应该使用它来插入超过几个元素到一个不太小的向量中。尤其是，您不应该使用这种方法对一个向量进行排序，因为其插入排序算法的运行时间复杂度为O(n²)。

在这种情况下，BinaryHeap 可能是一个更好的选择。每次插入(push)仅具有 O(log n) 的运行时间复杂度，而不是 O(n)。如果您愿意，甚至可以通过 into_sorted_vec() 将其转换为排序的 Vec。您也可以继续使用堆而不进行转换。

- Lukas Kalbertodt

---

推送操作的时间复杂度为O(N)：O(log N)搜索 + O(N)插入。如果您按相反的顺序插入，则时间复杂度为O(N²)，而不是二叉堆的O(N log N)。 - Kijewski