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

ドキュメントは、「バイナリヒープにベクトルを変換するにはその場で行うことができます」が、私は、トラブル動作するものを作るが生じていますと述べていますインプレースで行うことができます（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があります、したがって、インプレースです。重要な点は、BinaryHeapがのデータを所有しており、すべての内部を世界に公開していないことです。

あなたが求めているのは、rebuildをユーザ提供のベクターで呼び出すことです。私にとって、これは疑わしい有用性を持っていますが、あなたはいつもそれを公開するためにRFCを提出することができます。

Answer 2

あなたは&mut参照の後ろから何かを「動かす」ためmem::replaceを使用することができます。

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を値で借りるのに役立つクレートがあります。しかし、私は今それを見つけることができません。 borrow_by_valueが値によってあなたにVecを与え、いくつかのより多くの危険なコード（おそらくptr::write）で逆*listからVecを置くいくつかの危険なコード（おそらくptr::read）を使用しています

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

：それは次のようになります。実際の実装は、何らかの形でパニックからあなたを守るために少し複雑になるかもしれません。知りません。もしそうでなければ、結局それを使うのは避けるべきでしょう。

編集：私が話していた木箱はtake_mutです。このようなものをstd::memに追加するにはRFCさえあります。