问题标签 [heap]

当使用数组存储所有元素时，您使用什么样的数学来遍历 4 堆？具体来说，如何找到特定叶子的父节点的索引？

假设我有以下数组：

0|1|2|3|4|5|6|7|8|9|10|... 等

然后从堆中构建堆，其中 1 是根，2..5 是它的孩子，6..9 是 2 的孩子等等。

如果我需要找到（例如）6 的父母，我需要的数学究竟是什么？

我有一个事件优先级队列，但有时事件优先级会发生变化，所以我想将事件请求者的迭代器维护到堆中。如果优先级发生变化，我希望在 log(n) 时间内调整堆。我将始终只有一个迭代器指向堆中的每个元素。

我正在使用一个优先级队列，它最初将其元素的优先级基于启发式。随着元素出列，启发式方法会更新，并且当前队列中的元素可能会增加其键。

我知道有些堆（特别是斐波那契堆）已经摊销了 O(1) 减少键操作，但是是否有任何堆结构在增加键操作上有类似的界限？

对于我的应用程序，这远非性能问题（二进制堆工作正常），这实际上只是学术好奇心。

编辑：澄清一下，我正在寻找一种数据结构，其增加键操作的时间比 O(logn) 快，而不是减少键。我的应用程序从不减少密钥，因为启发式高估了优先级。

I'm kind of stuck with my heap sort here in php:

I can't get to sort the array, any idea what's wrong?

我在一个我有点懒惰地实现的程序中发现了一个有趣的错误，我想知道我是否正确理解了它。简短的版本是Python 的heapq实现实际上并不对列表进行排序，它只是以以堆为中心的方式对列表进行摸索。具体来说，我期望heapify()生成一个有序列表，以有序的方式促进列表理解。

使用优先提示示例，如 Python 文档中所示：

结果是

我们注意到，这不是列表的原始排序，但显然是一些以堆为中心的排序，如此处所述。我懒洋洋地期待这个完全订购。

作为测试，通过 heapify() 运行列表不会导致任何变化（因为列表已经按堆排序）：

而使用函数遍历列表会heappop()导致按预期排序：

因此，它似乎heapq不会对列表进行排序（至少在这个词的人类意义上），而是heappush()andheappop()函数能够理解堆排序的列表。

结果：堆化列表上的任何切片和列表理解操作都将产生无序结果。

这是真的吗？这总是真的吗？

（顺便说一句：WinXP 系统上的 Python 3.0.1）

可能重复：
免费商店的“堆”一词的由来是什么？

为什么堆叫堆？我的意思是我们动态分配位的内存位。

我使用的是SQL Server 2008。我知道如果一个表没有聚集索引，那么它被称为堆，否则存储模型称为聚集索引（B-Tree）。

我想了解更多关于堆存储的确切含义、它的外观以及它是否被组织为“堆”数据结构（例如最小堆、最大堆）的更多信息。有什么推荐的读物吗？我想要更多的内部知识，但不要太深。:-)

提前谢谢，乔治

我已经在 J​​ava 中研究斐波那契堆实现大约一周了。它是基于 CLRS 书的实现。

我想看看与 Java 的默认 PriorityQueue 相比，在我正在处理的副项目中使用它是否会获得任何性能提升。[Java 中的默认实现是基于数组的，因此更加本地化。尽管复杂度更高，但它仍可能优于 F-Heap]。

我的问题似乎源于删除 min 元素后堆的合并部分。我不断收到 arrayindexoutofboundsexceptions 抛出。特别是在while循环中，当它合并具有相同度数的所有节点时。它超出了 D() 函数设置的范围。

所以要么我的 D() 函数是错误的，我不认为它是错误的，要么是发生了其他事情。最有可能与副作用有关。

代码位于此处。我一直在尝试调试这个大约一周，现在很幸运。我错过了一些明显的东西吗？

我需要为堆实现提取最小值（如果可能，在 c++ 中），无法从 STL 堆中获取此方法。

我知道可以在 O(log n) 中实现减少键功能，但我不知道如何？