Взять элемент с наименьшим значением из HashSet?

Question

Я пытаюсь создать кучу с помощью метода, который возвращает узел с минимальным значением f, и в то же время удаляет его из самой кучи.

Куча все еще должна бытьможет использоваться впоследствии, только без удаленного значения:

Структура Node и ее реализация:

use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Node {
    x: f64,
    y: f64,
    f: f64,
}

impl Node {
    fn to_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Node) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl Eq for Node {}

impl Hash for Node {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.to_bits().hash(state)
    }
}

Структура Heap:

use std::f64;
use std::collections::HashSet;

#[derive(Debug)]
struct Heap {
    pool: HashSet<Node>,
}

impl Heap {
    fn add(mut self, node: Node) -> Heap {
        self.pool.insert(node);
        self
    }

    fn consume(mut self) -> Node {
      // find the node with minimum f-value in self.pool
      // and "take" it, aka remove it from the pool
      // and then return it
      Node { x: 0.0, y: 0.0, f: 0.0 } // dummy node so that the code compiles
    }
}

Иmain function:

fn main() {
    let n1 = Node { x: 10.0, y: 11.0, f: 5.0 };
    let n2 = Node { x: 11.0, y: 12.0, f: 7.0 };
    let n3 = Node { x: 12.0, y: 13.0, f: 3.0 };
    let n4 = Node { x: 14.0, y: 14.0, f: 4.0 };

    let mut heap = Heap { pool: HashSet::new() };
    heap = heap.add(n1);
    heap = heap.add(n2);
    heap = heap.add(n3);
    heap = heap.add(n4);

    let minimal_n1 = heap.consume();
    println!("{:?}", minimal_n1);
    // should print
    // Node { x: 12.0, y: 13.0, f: 3.0 }

    let minimal_n2 = heap.consume();
    println!("{:?}", minimal_n2);
    // should print
    // Node { x: 14.0, y: 14.0, f: 4.0 }

    println!("Heap has {} nodes", heap.pool.len());
    // should print
    // Heap has 2 nodes
}

Вот то, что я до сих пор пробовал в отношении consume:

fn consume(mut self) -> Node {
    let mut min_f = f64::MAX;
    let mut min_node: Option<&Node> = None;

    for n in self.pool.iter() {
        if n.f < min_f {
            min_f = n.f;
            min_node = Some(n);
        }
    }

    self.pool.take(&min_node.unwrap()).unwrap()
}

Проблема в том, что self.pool заимствовано неизменнометод iter(), и, следовательно, self.pool.take() не может заимствовать его в одно и то же время.

Каков наилучший подход, чтобы этот метод consume принимал и возвращал узел с минимальным значением f -значение среди pool?

Примечания:

• a Набор (или Карта) необходим, потому что другие методы должны получить любой Узел в O (1)
• Я не использую упорядоченный набор (который легко решит вышеуказанную проблему), потому что операции добавления / обновления должныstay O (1)
• К heap необходимо получить доступ после удаления узла минимального-f, как показано в примере

Answer 1

К счастью, поскольку вы берете self по значению, эту проблему легко решить.Просто отбросьте все, что не является минимальным Node:

fn consume(self) -> Node {
    self.pool
        .into_iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .expect("There was no minimum")
}

Если вам нужно сохранить Heap впоследствии, вам нужно отсоединить найденное значение от кучи, прежде чем удалять его.Клонирование - самое простое решение:

fn consume(&mut self) -> Node {
    let min = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .cloned()
        .expect("There was no minimum");

    self.pool.remove(&min);

    min
}

Для этого требуется выполнить «дополнительный» поиск хеша.Поскольку вы перебираете весь HashSet, похоже, это будет сравнительно небольшая стоимость.

---

Если вы не можете легко клонировать элемент, пристегнитесь.Используя идеи Как реализовать HashMap с двумя ключами? , мы можем построить объектный признак , который можно использовать для поиска ключа на основе параллельных, но эквивалентных реализаций хеширования / равенства:

use std::borrow::Borrow;

trait Key {
    fn as_bits(&self) -> u128;
}

impl Key for Node {
    fn as_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl Key for u128 {
    fn as_bits(&self) -> u128 { *self }
}

impl<'a> Hash for Key + 'a {
    fn hash<H: Hasher>(&self, h: &mut H) {
        self.as_bits().hash(h)
    }
}

impl<'a> PartialEq for Key + 'a {
    fn eq(&self, other: &Self) -> bool {
        self.as_bits() == other.as_bits()        
    }
}

impl<'a> Eq for Key + 'a {}

impl<'a> Borrow<Key + 'a> for Node {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

impl<'a> Borrow<Key + 'a> for u128 {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

С помощью этой поддержки мы можем преобразовать найденный элемент в облегченный собственный ключ, а затем снова посмотреть его, используя его:

fn consume(&mut self) -> Node {
    let min_key = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .map(Node::as_bits)
        .expect("There was no minimum");

    let min_key: &Key = min_key.borrow();
    self.pool.take(min_key).unwrap()
}