| RMVL 2.4.0 Robotic Manipulation and Vision Library

载入中...
搜索中...
未找到
支持随机访问的堆

作者
  赵曦

日期
  2023/01/11

上一篇教程：并查集
下一篇教程：ONNX-Runtime 分类网络部署库

相关类 rm::RaHeap

# 1 基本用法

rm::RaHeap 的基本用法与标准库中 std::priority_queue 的用法基本一致，都具有以下操作：

成员方法 | 含义
--- | ---
rm::RaHeap::empty | 判断堆是否为空
rm::RaHeap::size | 获取堆的大小
rm::RaHeap::top | 获取堆顶元素
rm::RaHeap::pop | 弹出堆顶元素
rm::RaHeap::push | 压入堆顶元素

可参考以下文档：

- C++ 标准库——优先队列

# 2 扩展用法

除此之外，RaHeap 还提供了以下扩展用法：

成员方法 | 含义
--- | ---
rm::RaHeap::update | 更新某个元素为新值（不存在则直接返回）
rm::RaHeap::erase | 删除某个指定元素（不存在则直接返回）
rm::RaHeap::extract | 返回堆的底层容器

# 3 例题

Dijkstra + 堆优化

使用 RaHeap：

using Pair = pair<Node *, int>;
struct Comp {
bool operator()(const Pair &p1, const Pair &p2) {
return p1.second > p2.second;
}
};
unordered_map<Node *, int> dijkstra(Node *head) {
RaHeap<Pair, vector<Pair>, Comp> node_heap;
node_heap.push({head, 0});
unordered_map<Node *, int> distanceMap;
distanceMap[head] = 0;
while (!node_heap.empty()) {
auto &[node, distance] = node_heap.top();
node_heap.pop();
for (auto edg : node->edges) {
if (distanceMap.find(edg->to) == distanceMap.end()) {
node_heap.push({edg->to, edg.weight + distance});
distanceMap[edg->to] = edg.weight + distance;
} else if (edg.weight + distance < distanceMap[edg->to]) {
node_heap.update({edg->to, distanceMap[edg->to]},
{edg->to, edg.weight + distance});
distanceMap[edg->to] = edg.weight + distance;
}
}
}
return distanceMap;
}