AyB*_*Bay 1 c++ heap priority-queue map binary-search-tree
我对二进制搜索树和二进制堆上的find_min操作的运行时有些困惑.我知道在二进制堆中返回min是一个O(1)操作.我也理解为什么理论上,返回二进制搜索树中的最小元素是O(log(N))操作.令我惊讶的是,当我读到C++ STL中的数据结构时,文档声明将迭代器返回到映射中的第一个元素(与返回最小元素相同)是在恒定时间内发生的!难道这不能以对数时间返回吗？我需要有人帮助我理解C++正在做什么,以便在不变的时间内返回.因为那时,在C++中真正使用二进制堆是没有意义的,因此地图数据结构将支持在常量时间中检索min和max,在O(log(N))中删除和搜索并保持一切排序.这意味着数据结构具有BST和二进制堆的优点,所有这些都捆绑在一起!
我和一位采访者谈论过这个问题(不是真正的争论),但我试图向他解释,在C++中,C++(这是一种自平衡的二元搜索树)中的map中的min和max返回是在恒定的时间内发生的.他感到困惑,不停地说我错了,二进制堆是要走的路.澄清将非常感激
通过在地图的头部结构中存储对RB树的最左侧和最右侧节点的引用来实现最小值和最大值的恒定时间查找.这里有一个建议F ROM的RB-树的源代码,模板从实施std::set,std::map以及std::multimap推导:
标题单元不仅与根连接,而且还与树的最左边节点保持连接,以启用恒定时间
begin(),并与树的最右边节点一起使用,以便在与通用集算法一起使用时启用线性时间性能(set_union,等等.)
这里的权衡是需要维护这些指针,因此插入和删除操作将有另一个"内务操作".但是,插入和删除已经在对数时间内完成,因此维护这些指针没有额外的渐近成本.