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

Question

I have written a small snippet, to find the shortest path between two nodes in a Min Heap.

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;
}

Is there a better way to do this with better average case? Just learning.

Edit:

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

To make it simple, lets say this array is a binary heap. The root is 1, and shortest path between lets say, 5 and 7 is given by shortestPath(5, 7).

Answer 1

if I'm right i and j are indices of nodes stored in the array

indices make a special binary tree then count how many nodes are in paths from LCA(i, j) to i and from LCA(i, j) to j

(LCA -> Lowest Common Ancestor)

this can be done in O(log N) as your code runs in O(log N)

but in shorter implementation:

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;
}