最大节点堆 java

Question

我目前需要实现最大节点堆，我的节点 class 跟踪数据、父节点以及左右子节点。我的最大堆插入方法需要永远填充 100 个字符串的数组。这是我的代码：`

public void insert(String name) {
MyNode node = new MyNode(name);
if (root ==null) {
        root = node;

    }
    else {
        MyNode parent = findSpot(root);
        if(parent.lChild==null) {
            parent.lChild=node;
            node.setParent(parent);

        }
        else {
            parent.rChild=node;
            node.setParent(parent);

        }


    }


}

public MyNode findSpot(MyNode curr) {
    if (curr.lChild == null) {
        return curr;
    }
    else if (curr.rChild==null) {
        return curr;
    }
    else {
        if (findSpot(curr.lChild).findHeight(root, curr, 1) > findSpot(curr.rChild).findHeight(root, curr, 1)) {
            return findSpot(curr.lChild);
        }
        else {
            return findSpot(curr.rChild);
        }
    }
}`

如果有人在代码中提供建议或告诉我哪里出了问题，我们将不胜感激。

Answer 1

如果您想查看 为什么 您的 findSpot 函数花费了这么长时间，请在开头添加一行输出 "findSpot <node>"，其中正在搜索的节点的详细信息。你会发现递归算法被调用了很多次。看起来 findHeight 也经常被调用。我不确定，但看起来您正在对每次插入进行详尽的树搜索。

二叉堆必须保持形状属性：它是一个完整的二叉树，除了最下面的一行可能是left-filled。因此，如果知道堆中有多少个节点，就可以轻松找到下一个节点的插入点。考虑这个堆：

      1
  2       3
4   5   6

堆中有6个节点。每当堆中有 6 个节点时，树将如下所示，下一个节点的插入点将是最右边节点（在本例中为 3）的右子节点。

有趣的是，节点号的二进制表示告诉我们该节点在哪里。比如6在二进制中就是110。去掉第一个数字 1，剩下 10。现在，从根开始，取数字中的下一个数字，如果数字为 0，则向左移动；如果数字为 1，则向右移动。然后取下一个数字，执行相同的操作。重复直到你运行个数字。

在 6 的情况下，我们将从根向右转到节点 3，然后向左转到节点 6。

添加新节点时，增加计数并按照上述步骤定位插入点。 7 在二进制中是 111。你砍掉高位，留下 11。然后，从根开始向右，插入点是节点 3 的右子节点。

当然，一旦你把节点放在树中以满足形状属性，你必须做标准的re-heapify来调整树中的节点，以便堆属性得到维护。

最大节点堆 java

Max heap of nodes java

java

heap

nodes

max-heap