Анализ размера кучи Фибоначчи (x) в CLRS имеет недостаток?

Во 3-м издании CLRS "Введение в алгоритмы", стр.525, когда анализируется нижняя граница размера (x), есть предложение, которое я цитирую как "поскольку добавление дочерних элементов в узел не может уменьшить размер узла, значение Sk увеличивается монотонно с к ". Но на самом деле, я думаю, что могу привести контрпример, чтобы показать, что Sk не обязательно монотонно увеличивается с k. На следующем графике степень узла с ключом =1 равна 2, и нет другого узла со степенью 2. Таким образом, S2=8. Аналогично, S3=6. Но теперь S3 меньше, чем S2, что означает, что Sk не увеличивается монотонно с k вообще.

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

Куча может быть получена из неупорядоченного биномиального поддерева, выполняя серию разрезов и каскадных разрезов.

Я хочу знать, является ли вышеуказанная структура допустимой кучей Фибоначчи. Если это так, то это также правильный контрпример.

Источник

1 ответ

Решение

Sk определяется как наибольшая нижняя граница, так что каждое поддерево степени k во всех возможных кучах Фибоначчи имеет по крайней мере Sk потомков.

Источник
Другие вопросы по тегам