查找堆深度比 O(n^2) 更快

Question

帮我优化一下算法。我在数组中有一个堆。数组中的每个数字表示父级。根是-1。我需要找到堆的深度。示例：

数组是 4 -1 4 1 1

答案是3。

这是我的代码

static int findMax(int[] mas) {
    int a[] = new int[mas.length];
    a[pos] = 1;
    int max = 0;

    for (int j = 0; j < mas.length; j++) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0 && a[mas[i]] != 0) {
                a[i] = a[mas[i]] + 1;
                if (a[i] > max)
                    max = a[i];
            }
        }
    }
    return max;
}

where pos - 根的位置。

我也用递归解决了这个问题。但是测试也给了我"Time limit exceeded"。

static class Node {
        static int nodesCount = 0;

        int val;
        int deep;
        List<Node> childrens = new ArrayList<>();
        static Set<Integer> deeps = new HashSet<>();

        public Node(int val, int deep) {
            this.val = val;
            this.deep = deep;
            deeps.add(deep);
            nodesCount++;
        }

        public List<Node> getChildrens() {
            return childrens;
        }

        public int getDeep() {
            return deep;
        }
    }
static int findMax(int [] mas){
    Node head = null;
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == -1)
            head = new Node(i, 1);
    }
    fillChildren(head, mas);
    return Node.deeps.stream().max(Comparator.naturalOrder()).get();
}

private static void fillChildren(Node head, int[] mas) {
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == head.val) {
            Node child = new Node(i, head.getDeep() + 1);
            head.getChildrens().add(child);
            fillChildren(child, mas);
        }
    }
}

Answer 1

虽然您可以根据父级数组在 O(n) 中找到最大深度，如 Matej 所述，但将该数组转换为更容易从父级方向导航的树结构可能是值得的到子节点。您已经使用 Node class 执行此操作，但是您的 fillChildren 方法具有 O(n²) 的复杂性，因为您必须一次又一次地扫描整个数组以找到当前节点的子节点.

相反，您可以创建一个 Map<Integer, Set<Integer>>，将节点映射到它们的子节点。这样，您可以在 O(n) 中在数组上的单个循环中创建整个树。

static Map<Integer, Set<Integer>> makeTree(int[] parents) {
    Map<Integer, Set<Integer>> tree = new HashMap<>();
    for (int i = 0; i < parents.length; i++) {
        tree.computeIfAbsent(parents[i], x -> new HashSet<>()).add(i);
    }
    return tree;
}

然后，您可以轻松编写一个递归函数来获取树的最大深度：

static int depth(Map<Integer, Set<Integer>> tree, int node) {
    return tree.containsKey(node) 
            ? 1 + tree.get(node).stream().mapToInt(n -> depth(tree, n)).max().getAsInt()
            : 0;
}

如果数组表示一棵树，则这两个步骤的复杂度都是 O(n)，因为每个节点只访问一次。如果数组还可以显示有向图，则应跟踪之前已经访问过的节点。对于您的示例，请像这样使用它：

int[] array = {4, -1, 4, 1, 1};
Map<Integer, Set<Integer>> tree = makeTree(array);
System.out.println(depth(tree, -1)); // 3

与任何递归算法一样，如果树非常非常深，这可能会达到最大递归深度。它可以使用 Stack 以迭代方式重写，但不会那么简洁。

Stack<Integer> stack = new Stack<>();
stack.add(-1);
int[] depth = new int[array.length];
while (! stack.isEmpty()) {
    int node = stack.pop();
    for (Integer child : tree.getOrDefault(node, Collections.emptySet())) {
        depth[child] = node == -1 ? 1 : depth[node] + 1;
        stack.add(child);
    }
}
System.out.println(IntStream.of(depth).max().getAsInt());

Answer 2

记住数组中已访问节点的深度。开始从第一个输入元素遍历到它的根，然后回溯存储深度到已访问节点数组。在从 child 到 parent 的每次跳跃中检查深度是否已经计算。如果是，则不必第二次走该路线，可以直接使用 pre-calculated 值。将是 O(n)。

Answer 3

为了证实 Matej 的回答，这里是伪代码。

为每个节点关联一个D字段，
初始化所有D为-1,
从每个节点开始，沿着父链，直到到达一个非负 D 的节点，
如果到达根，将其D设置为0，
向后追踪链，不断更新 D。

链遍历在遇到第一个非负节点时停止，所有中间节点都变为非负。所以负节点只被访问一次，这证明了 O(n) 行为。

更新链中的所有节点至关重要，否则可能会多次访问相同的节点。在最坏的情况下，这可能会导致 O(n²) 次操作。

值得注意的是，该算法需要一个栈来实现向后遍历。在最坏的情况下，堆栈深度可以达到 n，增加额外的 O(n) 存储 space（或者堆栈溢出的风险是不小心）。

一个更好的选择可能是使用遍历节点的D字段来存储"return index"并形成一个临时的反向链。

Answer 4

我们所需要的只是一张指示 children 所在位置的地图，然后执行广度优先搜索。正如我们在下面的输出中看到的，复杂度为 O(n)。

function f(A){
  let map = {};
  
  A.map((parentIdx, childIdx) => {
    if (map[parentIdx])
      map[parentIdx].push(childIdx);
    else
      map[parentIdx] = [childIdx];
  });
  
  let maxDepth = 0;
  let queue = [[-1, 0]];
  
  while (queue.length){
    const [node, depth] = queue.shift();

    console.log(
      `node: ${node}, children: [${map[node] || ''}], ` +
      `current depth: ${depth}`);

    maxDepth = Math.max(maxDepth, depth);
    
    if (map[node])
      for (let child of map[node])
        queue.push([child, depth + 1]);
  }
  
  return maxDepth;
}

var arr = [4, -1, 4, 1, 1];
console.log(f(arr));

查找堆深度比 O(n^2) 更快

Find heap depth faster than O(n^2)

java

algorithm

heap