Как узнать степень числа, которая является средним арифметическим степеней двух чисел?

Question

[BitNeBolt]

В задании нужно уменьшить количество сравнений при добавлении элемента в бинарную кучу до log(log(n)), для этого нужно использовать бин. поиск. С самим алгоритмом я разобрался, но не могу понять, как лучше рассчитывать индексы.

Например, новый элемент добавляется на индекс 18 (куча ориентирована на минимум),

в массиве находятся следующие значения

a[18] = 1.5
a[9] = 9
a[4] = 2.5
a[2] = 2
a[1] = 1

Мне нужно сравнить a[4] и a[18]. Степень 4 - это среднее арифметическое степеней 2 в числе 1 и 18 (округленную вниз). Как можно узнать эту степень?

Comments

[dmshar]

Переведите пожалуйста:
нужно сравнить a[4] и a[18]. Степень 4 - это среднее арифметическое степеней 2 в числе 1 и 18 (округленную вниз
Что такое "степень 4"?
Как может быть степень равной среднему арифметическому?
В числе 1 и 18 или все-таки в числах?
И вообще, у вас в массиве, на который вы отображаете свою кучу, элементы должны идти подряд, а не с пропусками по индексам как вы нарисовали.

[BitNeBolt]

dmshar, я плохо объяснил.
Элементы выстроены правильно, но я решил привести пример, когда к куче, в которой уже 17 элементов добавить ещё один. В таком случае 9, 4, 2, 1 - индексы родителей (9 для 18, 4 для 9 и т.д.)

Логарифм (с осн. 2) 18, округленный вниз - это 4, 1 - это 0. Среднее 4 и 0 - это 2. Нужно сравнить ключ с элементом по индексу 2^2=4.

[dmshar]

BitNeBolt,

Нужно сравнить ключ с элементом по индексу 2^2=4.

-- зачем ключ сравнивать с элементом??? И что-такое в вашем представлении "ключ"? - Это индекс? Или сам элемент? А ничего другого в массиве бинарного дерева быть не может.
Если вам надо найти индекс родителя - то это либо индекс элемента/2 либо (индекс элемента-1)/2 в зависимости от четности-нечетности самого индекса.
Если надо от элемента перейти к его наследникам - это тоже делается по индексам.
Какую вообще задачу вы пытаетесь решить?
Откуда у вас вылазят степени и логарифмы?

[BitNeBolt]

Вот задание:

Быстрая вставка. Разработайте для API-интерфейса MinPQ реализацию на ос нове сравнений, такую, чтобы операция вставить выполняла ~log logN сравне ний, а операция удалить наименьший выполняла -2logN сравнений. Совет: для поиска предка в методе swim() используйте бинарный поиск по родительским указателям.

Нужно сравнивать элемент, находящийся по найденному индексу, с элементом, который нужно вставить.

Answer 1

[Wataru]

Странное задание. Какая польза от этого сокращения сравнений, если всего в результате вставки переместится до O(log n) элементов?

Но, если так надо, то вам нужно для каждого числа сначала узнать номер старшего ненулевого бита (most significat bit - MSB), и потом сдвинуть верхнее число вправо на половину разницы в позициях старших битов.

1 = 0000001b, msb = 0
18 = 0010010b, msb = 4

Разность - 4 разряда. Значит, надо сдвигать на 2 разряда вправо:
18 >> 2= 0010010b >> 2 = 00100b = 4

Еще пример: для 4 и 18 msb были бы 2 и 4, разность -2. Сдвинув 18 на 2/2=1 разряд вправо, вы бы получили 9.

Чтобы эта оптимизация давала хоть какую-то пользу, надо находить msb очень быстро. Или предподсчитайте их для всех возможных индексов, или надейтесь, что в вашем языке есть встроенная функция, которая вызывает нужную инструкцию процессора, типа __builtin_clz.

Еще можно подсчитать msb только один раз для правой границы бинпоиска, а потом просто помнить его, ведь у средней точки - это среднее арифметическое (левая граница изначально 1 - у нее msb = 0). А потом в процессе бинпоиска надо просто хранить msb для двух границ и заменять известным значением середины один из концов.

Для предподсчета просто в цикле задавайте msb[i] = msb[i/2] + 1;