Java节点式最大堆实现求助：插入100条字符串效率极低

嘿，我一眼就瞅出问题所在了：你用findSpot(root)遍历整个堆来找有空位的父节点，这种方式每次插入都要从头扫一遍树，时间复杂度是O(n)，插100个元素就得做100次遍历，总复杂度直接飙到O(n²)，可不就慢嘛！

链式堆没法像数组堆那样直接用索引算父/子位置，但我们可以用队列来记录那些还没填满子节点的父节点，这样每次找父节点都是O(1)的操作，插入效率直接拉满：

• 初始化的时候搞个队列，插入根节点后就把根节点丢进队列。
• 每次插新节点时，取队列的队首节点：
  • 如果它没左子节点，就把新节点挂左子节点，然后把新节点加入队列（以后它也能当父节点），同时把当前队首节点留在队列里（它还有右子节点的空位）。
  • 如果它没右子节点，就把新节点挂右子节点，这时候这个父节点的两个坑都填满了，直接把它从队列里移除，再把新节点加进队列就行。
• 对了！别忘了最大堆的上浮调整，你之前的代码好像没做这个——光插节点不调整，那只是棵完全二叉树，根本不是最大堆！

import java.util.LinkedList;
import java.util.Queue;

public class MaxHeap {
    private MyNode root;
    private Queue<MyNode> availableParents;

    public MaxHeap() {
        availableParents = new LinkedList<>();
    }

    public void insert(String name) {
        MyNode node = new MyNode(name);
        if (root == null) {
            root = node;
            availableParents.add(root);
        } else {
            MyNode parent = availableParents.peek(); // 取队首但不移除
            if (parent.lChild == null) {
                parent.lChild = node;
                node.setParent(parent);
                availableParents.add(node); // 新节点未来可作为父节点
            } else {
                parent.rChild = node;
                node.setParent(parent);
                availableParents.add(node);
                availableParents.poll(); // 该父节点已无空位，移出队列
            }
            // 关键：最大堆上浮调整，保证父节点值大于子节点
            heapifyUp(node);
        }
    }

    // 上浮调整逻辑
    private void heapifyUp(MyNode node) {
        while (node.getParent() != null && node.getData().compareTo(node.getParent().getData()) > 0) {
            // 交换当前节点和父节点的数据
            String temp = node.getData();
            node.setData(node.getParent().getData());
            node.getParent().setData(temp);
            // 继续往上调整
            node = node.getParent();
        }
    }

    // 你的MyNode类实现示例
    private static class MyNode {
        private String data;
        private MyNode parent;
        private MyNode lChild;
        private MyNode rChild;

        public MyNode(String data) {
            this.data = data;
        }

        // 必要的getter和setter
        public String getData() { return data; }
        public void setData(String data) { this.data = data; }
        public MyNode getParent() { return parent; }
        public void setParent(MyNode parent) { this.parent = parent; }
        // 左右子节点的getter/setter自己补全就行
    }
}

如果不是业务强制要求用链式结构，其实数组实现的最大堆效率更高——直接用索引计算父节点（(i-1)/2）和子节点（2i+1、2i+2），不需要维护节点间的引用，插入和调整都更快。但如果必须用链式，队列跟踪可用父节点就是最优解啦！

内容的提问来源于stack exchange，提问作者James