我读了一些关于二进制堆/优先级队列的内容,并决定尝试自己实现一个。我不是最有经验的程序员,如果你们能看看我的堆类并告诉我它是否是一个好的实现,我将不胜感激。
我可以在这里改进什么?欢迎任何反馈。
public class Heap<T extends Comparable<? super T>> {
private T[] array = (T[])new Comparable[10];
private int size = 0;
public void insert(T data) {
if(size+1 > array.length) expandArray();
array[size++] = data;
int pos = size-1;
T temp;
while(pos != 0 && array[pos].compareTo(array[pos/2]) < 0) {
temp = array[pos/2];
array[pos/2] = array[pos];
array[pos] = temp;
pos /= 2;
}
}
public T deleteMin() {
T min = array[0];
array[0] = array[size-1];
array[size-1] = null;
size--;
int pos = 0;
T temp;
boolean done = false;
while(pos*2+1 < size && !done) {
int minChild = pos*2+1;
if(array[minChild].compareTo(array[pos*2+2]) > 0) minChild = pos*2+2;
if(array[pos].compareTo(array[minChild]) > 0) {
temp = array[minChild];
array[minChild] = array[pos];
array[pos] = temp;
pos = minChild;
}
else done = true;
}
return min;
}
private void expandArray() {
T[] newArray = (T[])new Comparable[array.length*2];
for(int i = 0; i < array.length; i++)
newArray[i] = array[i];
array = newArray;
}
}
回答你的问题的最好方法是编写单元测试来测试你的实现是否可靠,并编写一些性能测试来测试你的实现是否相当快。在做这两件事的过程中,你还会发现你的实现是否易于使用。
问题内容: 我正在编写一个使用二进制搜索树存储数据的程序。在以前的程序中(无关),我能够使用Java SE6随附的实现来实现链表。二进制搜索树是否有类似的东西,还是我需要“从头开始”? 问题答案: 您可以使用。被实现为一棵红黑树,这是一个自平衡二进制搜索树。
问题内容: 我在将这两种算法结合在一起时遇到麻烦。我被要求修改以返回将元素插入数组的索引。然后有人要求我实现一个使用my 对随机生成的数组进行排序的。 我按照预期的方式工作,每当我单独测试它时都返回正确的索引。我写信是为了了解它是如何工作的,并使其也能工作。一旦将两者结合在一起,它就会崩溃。我知道我在一起实施起来不正确,但是我不确定问题出在哪里。 这是我得到的: 我在运行它时得到的返回值是。有什么
在作为二叉树实现的二进制最大堆中(其中每个节点存储指向其父节点、左子节点和右子节点的指针),如果有指向堆根的指针,将如何实现插入操作?应该发生的是节点首先作为最后一行的最后一个元素被插入。对于基于数组的实现,您可以添加到数组中,但是对于基于树的实现,您如何找到正确的位置呢?
本文向大家介绍Java 程序实现八进制转换为二进制,十进制,十六进制,包括了Java 程序实现八进制转换为二进制,十进制,十六进制的使用技巧和注意事项,需要的朋友参考一下 假设我们有一个八进制数字。要将八进制转换为其他进制,例如二进制,十六进制等,Java代码如下: 示例 输出结果 一个名为Demo的类包含一个名为“base_convert”的函数。此函数将整数从源基解析为目标基,将其转换为字符串
我正在一个数组< code>arr上写一个二进制堆。 除了叶节点,每个节点都有两个子节点。 根可以位于 或 公认的答案是为什么在数组实现的堆中索引0未使用?说更快。 但是答案下面的一条评论说大多数实现都将root放在。 将根放在 有什么好处?
6.10.1.结构属性 为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。 为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充。 Figure 1 展示了完整二叉树的示例。 Figure 1 完