优先级队列 - 二进制堆

我想实现一个优先级队列作为排序数组支持最小二进制堆。我试图让update_key函数在对数时间运行，但要做到这一点，我必须知道该数组中项目的位置。无论如何不使用地图来做到这一点？如果是这样，怎么样？谢谢优先级队列 - 二进制堆

2012-04-15 Richard

什么是update_key函数？ – DRVic 2012-04-15 02:06:22

函数更新元素的键，因为二进制堆包含一个键，元素对 – Richard 2012-04-15 02:54:56

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

如果这些假设是真的试试这个： 1）在你的堆找到你的项目（IE：二进制搜索，因为它是一个排序数组）。 2）更新你的密钥（你只是改变一个值，不变的时间） 3）从堆日志（n）中删除项目以重新组织。
4）将你的项目插入堆日志（n）。所以，你会有log（n）+ 1 + log（n）+ log（n），它减少到log（n）。

注意：这是分期付款，因为如果你不得不重新分配你的数组等等......这会增加开销。但是你不应该经常这样做。

来源

2012-04-15 03:45:54

我不认为他意味着排序数组。典型的二进制堆实现将元素保存在一个数组中，但只有heap属性需要为true。保持所有元素排序并仍然具有O（log（n））复杂度来插入和删除元素是不可能的我想。 – 2012-04-15 06:33:16

这很有道理。假设一个人使用真正的堆结构，堆的根节点只需要比两个孩子更好（就排序而言），那么每个孩子可以被认为是另一个堆的根，并且这是递归地应用的）。我不知道为什么昨晚我没有想到这一点。感谢您的澄清。 – 2012-04-15 13:51:15

这是数组支持的堆的权衡：你获得了优秀的内存使用（良好的局部性和最小的开销），但是你失去了元素的轨迹。要解决这个问题，你必须添加一些开销。

一个解决方案就是这样。该堆包含C*类型的对象。 C是int成员heap_index的类，它是堆阵列中对象的索引。无论何时移动堆阵列中的元素，都必须更新其heap_index以将其设置为新索引。因此需要一段时间才能找到元素（通过heap_index）和log（n）时间将其冒泡到正确的位置，因此Update_key（以及去除任意元素）是log（n）时间。

来源

2012-04-15 05:10:08

如果你真的想要改变任意元素的键，堆不是数据结构的最佳选择。什么它给你的是组合：

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

1.的一个好处是缺少指针意味着您可以大大减少对malloc/free（new/delete）的调用次数。的地图（在标准库作为一个平衡二叉树表示）为您提供了中间两个的这些，对任意键添加在

对数find()。

因此，尽管你可以附加其他数据结构的堆，存储在堆栈指针，然后通过指针进行比较运算解引用，你会很快发现自己与时间的复杂性和公正空间首先使用map。

来源

2012-04-16 11:29:10 DRVic

优先级队列 - 二进制堆

回答

相关问题