c++ - 最适合求最小值的数据结构

Question

什么是最适合保存一组对的数据结构，在这些数据对(k,v)中我必须进行与v找到最少元素的数量相同的更新量v？

我正在考虑将它们保留在 a 中，并在每次插入新对时map<pair<k,v>>找到最小的对（添加的数量非常少......）。v

每次我更新时，v我都会比较“最小”对，如果它更小，我会更新“最小”对。

我有更好的解决方案吗？

Answer 1

您的解决方案仅考虑新值低于旧最小值的情况。
如果旧的最小值增加，它将失败，您必须找到新的最小值。

那么我会保留2张地图：

map<k,v> kKeyMap;

multimap<v,&k> vValueMap;

使用 multimap 获得最小值（因为它可以处理具有相同 v 的多个 k）。
像常规地图一样，它是排序的，因此获取最低的只是获取地图中的第一项O(1)。

在每次更改时，您使用第一个映射 ( )查找kkKeyMap，并更改值O(logn)。
使用旧的v值从多图中删除旧的 (v,k) 值，然后添加新的 (v,k) 值。O（登录）

所以，你有 O(1) 查询最低，O(logn) 插入。假设 n = #k