3

我正在寻找可以使用Object[]数组而不是对象Node来实现的优先级队列的堆结构。

二进制堆当然可以很好地工作，n 元堆也是如此。Javajava.util.PriorityQueue是一个二进制堆，使用Object[]数组作为存储。

还有很多其他堆，例如斐波那契堆，但据我所知，这些需要使用节点来实现。从我的基准测试来看，我的印象是管理所有这些节点对象所付出的开销可能会耗尽所有获得的收益。我发现很难实现一个可以使用简单的数组支持的二进制堆来实现的堆。

所以我目前正在寻找也没有使用Node对象开销的高级堆/优先级队列结构。因为我希望它在现实中更快，而不仅仅是在复杂性理论中更好……而且现实中发生了更多事情：例如 CPU 有 L1、L2 和 L3 缓存等，它们确实会影响性能。

我的问题也集中在Java上，因为我在这里对内存管理几乎没有影响，并且没有struct像在 C 中那样的 s。由于内存管理开销，在 C 中实现时运行良好的许多堆在 Java 中变得昂贵和垃圾收集费用。

4

1 回答 1

3

几种不常见的堆结构可以通过这种方式实现。例如，在 Dijkstra 的平滑排序算法中使用的 Leonardo Heap 通常被实现为一个增加了两个机器字的数组。像二叉堆一样，数组表示是特定树结构（或者更确切地说是森林，因为它是树的集合）的数组表示。

杨树堆结构是作为理论上效率稍低但实际上效率更高的堆结构引入的，具有相同的基本思想 - 数据表示为具有一些额外小的状态信息的数组，并且是森林结构的压缩表示。

一个更规范的基于数组的堆是d-ary heap，它是二叉堆的自然概括，具有 d 个孩子而不是两个。

作为一个非常愚蠢的例子，排序数组可以用作优先级队列，尽管它非常低效。

希望这可以帮助！

于 2013-01-09T18:34:40.077 回答