使用std :: collections :: BinaryHeap就地heapsort

Question

我想在Rust中創建一個就地heapsort函數。在標準庫中，我發現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() 
} 

，「一個向量轉換成二進制堆可以就地完成」，但我有麻煩創建一個工程的文檔狀態在參考上，並可以在原地進行（heapsort<T: Ord>(list: &mut Vec<T>)）。我只能使用std::collections::BinaryHeap嗎？

Answer 1

我無法創建一個上的參考工作，可以就地

BinaryHeapis built on top of Vec做到這一點。當您從Vec創建新堆時，您必須授予它完整的所有權。然後它將確保矢量處於良好狀態以充當堆。

由於BinaryHeap不是建立在&mut Vec之上（它大多會有可怕的人體工程學），所以你不能這樣做。

目前還不清楚爲什麼你不只在矢量上使用slice::sort。

的文檔狀態，「一個矢量變換成二進制堆可以做到就地」

爲了澄清，所述文檔是正確的 - 有no extra memory allocation needed，因此它是就地。重要的是它的數據並不會將所有的內部信息公開給世界。

您要求的是可以在用戶提供的矢量上調用rebuild。對我來說，這有可疑的用處，但你總是可以提交一個RFC來公開它。

Answer 2

可以使用mem::replace爲「移動」從背後&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由等於一個空向量。在這種情況下，沒關係，因爲創建和刪除空的Vec很便宜。

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）。實際的實施可能會稍微複雜一點，以保護你免於恐慌。我不知道。如果不是，你應該儘量避免使用它。

編輯：我在說的箱子是take_mut。甚至有一個RFC添加這樣的東西到std::mem。