Макрос сдвига бит кучи для левого, правого и родительского

Question

Я читаю о кучах, которые описывают, что вы можете выполнять операции доступа к левому дочернему элементу, правому / левому дочернему элементу и PARENT с помощью операций битового сдвига. В то время как Левый и Родитель кажутся тривиальными, я не уверен с правильным. Должен ли я просто добавить один?

Вот выдержка из книги: MIT Введение в алгоритмы:

"Аналогично, процедура RIGHT может быстро вычислить 2i + 1, сдвинув двоичное представление i, оставленное на одну битовую позицию, и затем добавив 1 в качестве бита младшего разряда".

Операции доступа:

ЛЕВЫЙ: 2* я

i<<1

ПРАВО: 2* я + 1

(i<<1)+1

РОДИТЕЛЬ: I /2

i>>1

Answer 1

Сдвиг влево на одну битовую позицию на Int i эквивалентно 2*i

Если мы рассмотрим i как индекс массива:
- индекс левого ребенка можно получить с помощью:

i << 1

-индекс правильного ребенка

(i<<1)+1

-Родитель:

i>>1

(эквивалентно i/2)

Не забудьте, что в этом случае мы считаем, что начальный индекс массива равен 1.

Answer 2

Вот как работает куча - для каждого узла вы можете легко получить:

1. Родитель - просто разделите индекс узла на два (N / 2)
2. Левый ребенок - умножить индекс на два (N * 2)
3. Правый ребенок - умножить индекс на два и увеличить новый индекс на один (N * 2 + 1)

Нетрудно доказать, что два разных узла не могут иметь одного и того же ребенка.

Предположим, N1, N2 а также C являются кучей узлов. N1 != N2 а также C.is_child_of(N1) а также C.is_child_of(N2), где C.is_child_of(N) возвращается true когда C правый или левый ребенок N, Затем:

1. Если C левый ребенок обоих N1 а также N2, затем N1 * 2 = N2 * 2 <=> N1 = N2
2. Точно так же, если C правильный ребенок обоих N1 а также N2, затем N1 * 2 + 1 = N2 * 2 + 1 <=> N1 = N2
3. Если C левый ребенок N1 а также C правильный ребенок N2, затем N1 * 2 = N2 * 2 + 1 что неверно, потому что N1 * 2 четный и N2 * 2 + 1 странно

---

Обратите внимание, что ваши побитовые операции доступа некорректны - вы должны сдвигать индексы на один, а не на два, потому что N << M является N * 2^M, Я бы также предложил вам использовать простое деление / умножение вместо сдвига битов - компилятор знает, как оптимизировать ваш код.