java - 有没有更好的方法来找到最小堆中节点之间的最短路径

Question

我写了一个小片段，以找到最小堆中两个节点之间的最短路径。

public int shortestPath(int i, int j)
{
    int path = 0;
    int hi = Math.max(i, j);
    int lo = i + j - hi;
    while (hi > lo)
    {
        hi = hi / 2;
        path++;
    }
    if (hi == lo) return path;
    while (hi != lo)
    {
        if (lo > hi) lo = lo / 2;
        else      hi = hi / 2;
        path++;
    }
    return path;
}

有没有更好的方法可以用更好的平均情况来做到这一点？只是学习。

编辑：

int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};

为了简单起见，假设这个数组是一个二进制堆。根是 1，假设 5 和 7 之间的最短路径由 shortestPath(5, 7) 给出。

Answer 1

如果我是对的 i 和 j 是存储在数组中的节点的索引

索引创建一个特殊的二叉树，然后计算从 LCA(i, j) 到 i 和从 LCA(i, j) 到 j 的路径中有多少节点

（LCA -> 最低共同祖先）

这可以在 O(log N) 中完成，因为您的代码在 O(log N) 中运行

但在较短的实施中：

int shortestPath(int i, int j) {
    int path = 0;
    boolean b;
    while (i != j) {
        b = i > j;
        i >>= (b ? 1 : 0);
        j >>= (!b ? 1 : 0);
        path++;
    }
    return path;
}