代码之家  ›  专栏  ›  技术社区  ›  James

最大节点堆java

  •  -1
  • James  · 技术社区  · 6 年前

    我目前需要实现一个最大的节点堆,其中我的节点类跟踪数据、父节点,然后是左、右子节点。我的max-heap的insert方法要用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);
            }
        }
    }`
    

    如果有人提供建议或告诉我有什么问题,我们将不胜感激。

    1 回复  |  直到 6 年前
        1
  •  1
  •   Jim Mischel    6 年前

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

    二进制堆必须保持Shape属性:它是一个完整的二叉树,但最下面的一行可能是左填充的。因此,如果知道堆中有多少节点,就可以很容易地找到下一个节点的插入点。考虑一下这个堆:

          1
      2       3
    4   5   6
    

    堆中有6个节点。每当堆中有6个节点时,树将如下所示,下一个节点的插入点将是最右节点的右子节点(本例中为3)。

    有趣的是,节点号的二进制表示告诉我们该节点在哪里。例如,二进制中的6是 110 。去掉第一个数字1,剩下的是 10 。现在,从根开始,取数字中的下一个数字,如果数字为0,则向左,如果数字为1,则向右。然后取下一个数字,做同样的事情。重复此操作,直到数字用完。

    对于6,我们将从根向右转到节点3,然后向左转到节点6。

    添加新节点时,请增加计数,然后按照上面的过程定位插入点。7是 111 二进制格式。你砍掉高位,离开 11 。然后,从根开始向右,插入点是节点3的右子节点。

    当然,一旦将节点放置在树中以满足shape属性,就必须执行标准的重新heapify来调整树中的节点,以便维护heap属性。