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

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 是存储在数组中的节点的索引

indices 生成一棵特殊的二叉树，然后计算从 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;
}

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

Is there a better way to find shortest path between nodes in Min Heap

java

algorithm

shortest-path

min-heap