将元素插入到有序向量中的最有效方法是什么？

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分配成本.

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在这种情况下,A 可能是更好的选择.每个insert(push)的运行时复杂度仅为O(log n)而不是O(n).你甚至可以把它转换成一个有序Vec有into_sorted_vec(),如果你愿意的话.您也可以继续使用堆而不是转换它.