c++ - 优先队列 - 二叉堆

Question

我正在尝试将优先级队列实现为支持最小二进制堆的排序数组。我试图让 update_key 函数以对数时间运行，但要做到这一点，我必须知道该项目在数组中的位置。有没有办法在不使用地图的情况下做到这一点？如果是这样，怎么做？谢谢

Answer 1

如果您真的希望能够更改任意元素的键，那么堆并不是数据结构的最佳选择。它给你的是以下组合：

1. 紧凑的表示（没有指针，只有一个数组和一个隐式索引方案）
2. 对数插入，再平衡
3. 最小（最大）元素的对数去除。
4. O(1) 访问最小（最大）元素的值。-

1. 的一个附带好处是缺少指针意味着您对malloc/free( new/delete) 的调用要少得多。映射（在标准库中表示为平衡二叉树）为您提供了其中两个，添加

1. 任何键的对数find()。

因此，虽然您可以将另一个数据结构附加到您的堆中，将指针存储在堆中，然后通过指针取消比较运算符的引用，但您很快就会发现自己在时间和空间上的复杂性是map首先使用 a .

Answer 2

您的查找键功能应在 log(n) 时间内运行。您的更新（更改密钥）应该是恒定的时间。您的删除功能应该在 log(n) 时间内运行。您的插入功能应该是 log(n) 时间。

如果这些假设是真的，试试这个：1）在你的堆中找到你的项目（IE：二分搜索，因为它是一个排序的数组）。2）更新您的密钥（您只是更改一个值，恒定时间） 3）从堆日志（n）中删除该项目以重新堆放。
4）将您的项目插入堆日志（n）。

所以，你会得到 log(n) + 1 + log(n) + log(n) 减少到 log(n)。

注意：这是摊销的，因为如果你必须重新分配你的数组等......这会增加开销。但无论如何，你不应该经常这样做。

Answer 3

这就是数组支持的堆的权衡：您可以获得出色的内存使用（良好的局部性和最小的开销），但您会丢失元素的跟踪。要解决它，您必须增加一些开销。

一种解决方案是这样。堆包含类型为 的对象C*。C 是一个具有int成员的类heap_index，它是堆数组中对象的索引。每当您在堆数组中移动一个元素时，您都必须更新它heap_index以将其设置为新索引。

然后，Update_key（以及删除任意元素）是 log(n) 时间，因为找到元素（通过heap_index）需要恒定的时间，并且需要 log(n) 时间才能将其冒泡到正确的位置。