Сколько сравнений вызовет removeMin () в максимальной куче 7-го дерева?

Question

Предположим, что максимальная куча с 10 ^ 6 элементами хранится в полном 7-мерном дереве . Примерно сколько сравнений вызов removeMin () сделает?

• 5000
• 50
• 10 ^ 6
• 500
• 5

Мое решение: Количество сравнений должно быть равно количеству листовых узлов не больше, потому что в макс куча, мин. можно найти на любом из листовых узлов, которого нет в приведенных выше параметрах. Лучшим подходом было взять квадрат (логарифм от 10 ^ 6 до основания 7), который дает 50, но это только тогда, когда мы уверены, что минимальный элемент будет следовать одной ветви по дереву, что в случае максимальной кучи не верный. Надеюсь, ты сможешь помочь.

Answer 1

Не существует "естественного" способа удалить минимальное значение из максимальной кучи. Вам просто нужно посмотреть на все листовые узлы, чтобы определить, какой из них является минимальным.

Тогда вопрос в том, сколько всего конечных узлов. Интуитивно мы ожидаем, что доля узлов в куче, которые являются листьями, будет довольно близка к общему количеству узлов. Сделайте это до предела - если у вас есть куча в 1 000 000 штук, у вас будет один узел в верхнем слое, а все оставшиеся 999 999 элементов - в следующем слое. Даже в самом маленьком случае, когда куча представляет собой двоичную кучу, можно ожидать, что примерно половина элементов будет на нижнем уровне.

Точнее, давайте подумаем! Сколько листьев будет у семизначной кучи с n узлами? Итак, каждый узел в дереве будет либо

• листом, либо
• будет иметь семь дочерних узлов,

с одним возможным исключением, поскольку самая нижняя строка может быть неполной, может быть один узел с менее чем семью дочерними элементами. Поскольку это всего лишь один раз, мы можем игнорировать этот последний узел, когда имеем дело с миллионами элементов. Быстрое доказательство по индукции можно использовать, чтобы показать, что любое дерево, в котором каждый узел либо не имеет дочерних, либо семь дочерних узлов, будет иметь в семь раз больше листовых узлов, чем внутренних узлов (докажите это!), Так что мы ожидаем, что (7/8 ) тыс. узлов будут листами, всего 875 000 листов для проверки.

В результате лучшим ответом здесь будет примерно 10 ⁶ сравнений.

Answer 2

Элемент Min может быть любым из листьев максимальной кучи или любого типа, и там нет порядка. Все элементы от A [10 ^ 6/7 + 1] и далее (где A - массив, хранящий листья) являются листовыми узлами и должны быть проверены. Это означает 8571412 сравнений, чтобы найти минимум. После этого не существует простого способа «удалить» минимум, не создав зазор, который нельзя заполнить простым перемещением створок.

Это опечатка. Возможно, учитель хотел спросить removeMax, для которого ответ близок к 50 - см. Ниже:

Heapify выполняет 7 сравнений на уровень, поскольку каждый узел имеет 7 дочерних узлов. Если h - высота кучи, то это сравнения 7 * h.

Грубый анализ: (здесь ~ означает приблизительно) h ~ log_7 (10 ^ 6) = 7,1, следовательно, общее количество сравнений 7 * 7,1 ~ 50

Более точный анализ: 7-рядная куча имеют элементы: 1 + 7 + 7 ^ 2 + ... + 7 ^ h = 10 ^ 6

С левой стороны ряд геометрических c, который суммируется до: (7 ^ h -1 ) / 6 = 10 ^ 6

=> 7 ^ h = 6 * 10 ^ 6 + 1 => h = lg_7 (6 * 10 ^ 6 + 1) = 8 (приблизительно), следовательно, 7 * 8 = 56, все же из вариантов 50 - самый близкий.

* A - массив для сортировки кучи.