Есть ли лучший способ найти кратчайший путь между узлами в Min Heap

Question

Я написал небольшой фрагмент, чтобы найти кратчайший путь между двумя узлами в 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;
}

Есть ли лучший способ сделать это с лучшим средним случаем? Только учится.

Редактировать:

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

Для простоты предположим, что этот массив представляет собой двоичную кучу. Корень равен 1, а кратчайший путь между, скажем, 5 и 7 задается ShorttestPath(5, 7).

Answer 1

Если я прав, я и 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;
}