rust - 将元素插入已排序向量的最有效方法是什么？

Question

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

EventHandler<T>如下:

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

由于排序的工作方式，插入和排序效率低下，使用 O(n log n) time complexity and 2*n allocation cost .

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),
}

如果你想在你的 vector 中允许重复的元素并因此想要插入已经存在的元素，你可以写得更短:

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

---

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

因此您不应该使用它来将多个元素插入到向量中，向量的大小并不小。特别是，您不应使用此方法对向量进行排序，因为此插入排序算法的运行时间为 O(n²)。

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