我正在尝试将优先级队列实现为排序数组支持的最小二进制堆。我试图让update_key函数在对数时间内运行，但是要做到这一点，我必须知道该项目在数组中的位置。无论如何，有没有使用地图就可以做到这一点？如果是这样，怎么办？谢谢
最佳答案
如果您确实希望能够更改任意元素的键，则堆不是数据结构的最佳选择。它为您提供的是以下各项的组合：
紧凑的表示形式（没有指针，只有一个数组和一个隐式
索引方案）
对数插入，重新平衡
最小（最大）元素的对数去除。
O（1）访问最小（最大）元素的值。 --
1的附带好处是，缺少指针意味着您对malloc/free（new/delete）的调用大大减少了。
映射（在标准库中表示为平衡的二叉树）为您提供了其中的两个，
任何键上的对数find()。
因此，尽管您可以将另一个数据结构附加到堆上，将指针存储在堆中，然后使比较运算符通过指针取消引用，但您很快就会发现自己在时间和空间上的复杂性仅在于使用map第一名。
关于c++ - 优先队列-二进制堆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10158823/