当前位置: 首页 > 知识库问答 >
问题:

Java——我的二进制堆实现有多好?

湛安宁
2023-03-14

我读了一些关于二进制堆/优先级队列的内容,并决定尝试自己实现一个。我不是最有经验的程序员,如果你们能看看我的堆类并告诉我它是否是一个好的实现,我将不胜感激。

我可以在这里改进什么?欢迎任何反馈。

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;
    }
}

共有1个答案

甄飞飙
2023-03-14

回答你的问题的最好方法是编写单元测试来测试你的实现是否可靠,并编写一些性能测试来测试你的实现是否相当快。在做这两件事的过程中,你还会发现你的实现是否易于使用。

 类似资料:
  • 问题内容: 我正在编写一个使用二进制搜索树存储数据的程序。在以前的程序中(无关),我能够使用Java SE6随附的实现来实现链表。二进制搜索树是否有类似的东西,还是我需要“从头开始”? 问题答案: 您可以使用。被实现为一棵红黑树,这是一个自平衡二进制搜索树。

  • 问题内容: 我在将这两种算法结合在一起时遇到麻烦。我被要求修改以返回将元素插入数组的索引。然后有人要求我实现一个使用my 对随机生成的数组进行排序的。 我按照预期的方式工作,每当我单独测试它时都返回正确的索引。我写信是为了了解它是如何工作的,并使其也能工作。一旦将两者结合在一起,它就会崩溃。我知道我在一起实施起来不正确,但是我不确定问题出在哪里。 这是我得到的: 我在运行它时得到的返回值是。有什么

  • 在作为二叉树实现的二进制最大堆中(其中每个节点存储指向其父节点、左子节点和右子节点的指针),如果有指向堆根的指针,将如何实现插入操作?应该发生的是节点首先作为最后一行的最后一个元素被插入。对于基于数组的实现,您可以添加到数组中,但是对于基于树的实现,您如何找到正确的位置呢?

  • 本文向大家介绍Java 程序实现八进制转换为二进制,十进制,十六进制,包括了Java 程序实现八进制转换为二进制,十进制,十六进制的使用技巧和注意事项,需要的朋友参考一下 假设我们有一个八进制数字。要将八进制转换为其他进制,例如二进制,十六进制等,Java代码如下: 示例 输出结果 一个名为Demo的类包含一个名为“base_convert”的函数。此函数将整数从源基解析为目标基,将其转换为字符串

  • 我正在一个数组< code>arr上写一个二进制堆。 除了叶节点,每个节点都有两个子节点。 根可以位于 或 公认的答案是为什么在数组实现的堆中索引0未使用?说更快。 但是答案下面的一条评论说大多数实现都将root放在。 将根放在 有什么好处?

  • 6.10.1.结构属性 为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。 为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充。 Figure 1 展示了完整二叉树的示例。 Figure 1 完