В CLRS "Введение в алгоритмы", 3-е издание, стр.525, когда он анализирует нижнюю границу размера (x), есть предложение, которое я цитирую как "потому что добавление потомков к узлу не может уменьшить размер узла, значение Sk увеличивается монотонно с k ". Но на самом деле, я думаю, что могу привести контрпример, чтобы показать, что 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
Куча может быть получена из неупорядоченного биномиального поддерева, выполняя серию разрезов и каскадных разрезов.
Я хочу знать, является ли вышеуказанная структура допустимой кучей Фибоначчи. Если это так, то это также допустимый контрпример.