我正在尝试从头开始实现我自己的 PriorityQueue 类（不使用任何现有的 Java 导入或库）。我知道我想使用最小堆数据结构。但我将堆可视化为二叉搜索树上的一种形式。我应该使用链表样式节点来实现这个最小堆，还是应该使用数组？两者的好处或首选方法是什么？或者我可以使用第三种选择吗？
问问题
883 次
2 回答
1
在回答问题之前，请先看看这个。
但我将堆可视化为二叉搜索树上的一种形式。
这不是真的。堆是二叉树的一种形式，但不是二叉搜索树。请参阅二叉树和二叉搜索树之间的区别
现在，为了回答你的问题，我会选择某种数组形式。原因是我在实现堆时需要经常用索引信息计算我的孩子或我的父母。通常，它发生在以下计算中。
给定 n 是当前节点的索引，索引从 1 开始（为简单起见）
- 父母指数 = n/2
- 左子索引 = 2n
- 右孩子索引 = 2n+1
当您使用 LinkedList.get(n) 执行此操作时，它是 O(n)。在 ArrayList 或数组中，它是 O(1)。
于 2017-04-28T19:00:48.547 回答
0
我能想到的最简单的实现是使用 LinkedList 或 ArrayList ，它们根据优先级保持自身的排序顺序。然后，当需要从队列中删除某人时，您从列表的前面或后面删除（取决于您对数组的排序方式）。
于 2017-04-28T18:31:12.817 回答