c++ - 具有堆和映射等效功能的数据结构

Question

我想设计一个元素E的容器C。

E 有 2 个属性(优先级，名称)，容器中的所有元素都有唯一的“名称”

我想尽可能高效地支持此容器 C 上的以下操作。

1. insert:- 将 element1(name1, priority1) 插入到容器中:C.insert(element(name1, priority1))
2. 更新:- 将名称=name1 的元素的优先级更新为 priorityNew1:C[name1] = priorityNew1
3. delete:-删除name=name1的元素: C.delete(name1)
4. 获取并删除具有最高优先级的元素:C.pop()
5. 获取最高优先级的元素:C.peek()

基本上我想要 map 和 heap 的组合。映射在元素的“名称”上，堆放在元素的“优先级”上。最理想的是，我希望每个操作都是 O(1)。否则插入、更新、删除的复杂度为 O(log N)，弹出和查看的复杂度为 O(1)。

我可以想到以下两种方法

1) 使用元素的 HashMap ，根据名称进行哈希处理。所以插入更新删除是 O(1)pop 和 peek 是 O(N)，我们搜索整个容器以获得最高优先级。

2) 将 SQLite 与具有两列“名称”和“优先级”的表“元素”一起使用。运行时间将基于 SQLite 实现。

我有兴趣了解关于这个问题的更多想法，我正面临与此相关的现实世界问题。感谢您的投入。

Answer 1

如果每个操作的O(logN) 是可以接受的，显然boost::bimap就足够了。这就像一个双面std::map。通过同时维护两个 std::map 或编写自己的包装器，您可以获得几乎相同的结果(但为什么要这样做？)。具有自平衡功能的二叉搜索树具有用于最小检索的 O(logN)，其效率略低于堆。

如果效率真的那么重要，您应该使用堆和散列映射来实现自己的容器。然后，当您在堆中交换时，在 HashMap 中的堆数组中维护从 name 到订阅的映射。这为插入、删除、重新分配优先级 O(logN) 和 O(1) 中的最小/最大优先级元素。 (这不是小菜一碟，但也不乏味)