使用 std::collections::BinaryHeap 就地堆排序

In-place heapsort using std::collections::BinaryHeap

我想在 Rust 中创建一个就地堆排序函数。在标准库中,我发现 std::collections::BinaryHeap 看起来很有希望。我能够使用它来创建一个使用其参数的函数:

use std::collections::BinaryHeap;

fn heapsort<T: Ord>(list: Vec<T>) -> Vec<T> {
    let heap = BinaryHeap::from(list);
    heap.into_sorted_vec()
}

文档指出 "converting a vector to a binary heap can be done in-place",但我无法创建一个适用于参考并且可以就地完成的文档 (heapsort<T: Ord>(list: &mut Vec<T>))。我可以仅使用 std::collections::BinaryHeap 实现吗?

I am having trouble creating one that works on a reference and can do it in-place

BinaryHeapis built on top of Vec。当您从 Vec 创建一个新堆时,您必须赋予它完整的所有权。然后它将确保向量处于良好状态以充当堆。

由于 BinaryHeap 不是建立在 &mut Vec 之上(后者的人体工程学设计很糟糕),您不能那样做。

不清楚为什么不在矢量上使用 slice::sort

the docs state that "converting a vector to a binary heap can be done in-place"

澄清一下,文档是正确的 - 有 no extra memory allocation needed,因此它就位。重要的一点是 BinaryHeap 拥有自己的数据 并且不会向外界公开所有内部信息。

您要求的是能够在用户提供的向量上调用 rebuild。对我来说,这有可疑的用处,但您总是可以提交一个 RFC 来公开它。

您可以将 mem::replace 用于 "moving" 来自 &mut 参考资料的内容:

use std::collections::BinaryHeap;
use std::mem;

fn heapsort<T: Ord>(list: &mut Vec<T>) {
    let tmp = mem::replace(list, Vec::new());
    let heap = BinaryHeap::from(tmp);
    *list = heap.into_sorted_vec();
}

因此,有一段时间 *list 等于一个空向量。在这种情况下没关系,因为创建和删除空 Vecs 非常便宜。

IIRC 甚至有一个板条箱可以帮助按价值借用一些 *mutref,而无需在借用期间就地使用虚拟值。但我现在找不到它。它看起来像这样:

fn heapsort<T: Ord>(list: &mut Vec<T>) {
    borrow_by_value(list, |tmp| {
        BinaryHeap::from(tmp).into_sorted_vec()
    });
}

其中 borrow_by_value 使用一些不安全代码(可能是 ptr::read)按值给你 Vec 并将 Vec 放回 *list使用一些更不安全的代码(可能 ptr::write)。实际的实现可能会稍微复杂一些,以保护您免受恐慌。我不知道。如果没有,您可能应该避免使用它。

编辑:我说的 crate 是 take_mut. There is even an RFC 将这样的东西添加到 std::mem