Lib.rs

HashHeap 是一种将优先队列与哈希表合并的数据结构。使用二叉堆实现的优先队列的缺点是搜索需要 O(n) 的时间。其他操作，如任意删除或替换值，也需要 O(n) 的时间。

然而，在 HashHeap 中，值与键配对。键是可哈希的（:Hash+Eq）且值是可比较的（:Ord）。从概念上讲，内部 HashMap 将键映射到内部向量中值存储的 索引。需要交换值的所有堆操作必须保持 hashmap 的一致性。虽然实际的实现要复杂一些，因为它避免了所有克隆，但这种安排允许搜索在（平均情况下）O(1) 的时间内完成。删除或替换值，这也会要求值在堆中向上或向下移动，可以在 O(log n) 的时间内完成。

考虑对象优先级可能会 改变 的可能性。这需要找到对象然后将其移动到队列的顶部或底部。在大多数优先队列实现中，这只能通过删除旧值并插入新值来实现。HashHeap 可以用于有效实现 Dijkstra 算法中的“开放”或“试探”队列。当找到更低成本的路径时，队列中该路径的位置必须更新。使用 HashHeap 可以在 O(log n) 的时间内完成此操作。

示例

  use hashheap::*;
  let mut priority_map = HashHeap::<&str,u32>::new_minheap();
  priority_map.insert("A", 4);   // O(1) average, O(log n) worst
  priority_map.insert("B", 2);
  priority_map.insert("C", 1);
  priority_map.insert("D", 3);
  priority_map.insert("E", 4);
  priority_map.insert("F", 5);
  priority_map.insert("A", 6);   // insert can also modify
  assert_eq!(priority_map.peek(), Some((&"C",&1))); // O(1)
  assert_eq!(priority_map.get(&"E"), Some(&4));     // O(1)
  assert_eq!(priority_map[&"F"], 5);                // O(1)
  priority_map.modify(&"F", |v|{*v=4;});            // O(log n)
  priority_map.remove(&"E");                        // O(log n)
  let mut total = 0;
  for (key,val) in &priority_map {
    total += val;
  }
  assert_eq!(total, 16);
  assert_eq!(priority_map.pop(), Some(("C",1)));    // O(log n)
  assert_eq!(priority_map.pop(), Some(("B",2)));
  assert_eq!(priority_map.pop(), Some(("D",3)));
  assert_eq!(priority_map.pop(), Some(("F",4)));    
  assert_eq!(priority_map.pop(), Some(("A",6)));    
  assert_eq!(priority_map.len(), 0);