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

Question

我想在 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 实现吗？

Answer 1

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 来公开它。

Answer 2

您可以将 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。

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

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

sorting

rust

heapsort