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

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

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

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


algorithm data-structures tree language-agnostic max-heap
person Hashir    schedule 06.05.2020    source источник
comment
логарифм от 10 ^ 6 до основания 7 составляет около 7, а не 50 ...   -  person Yonlif    schedule 06.05.2020
comment
Я думаю, что на самом деле вопрос заключается в том, какова временная сложность операции удаления минимума из максимальной кучи? И ответ на это O(n), поэтому ответ должен быть 10^6.   -  person Yonlif    schedule 06.05.2020
comment
Нет. Во-первых, я сказал, что квадрат log 10 ^ 6 равен 50. Во-вторых, я спрашиваю не о временной сложности, а об общем количестве сравнений, которые выполнит removeMin ().   -  person Hashir    schedule 06.05.2020
comment
Ваш ответ будет правильным, если вы написали min heap с помощью removeMin или если вы написали removeMax с max heap ... Хотя тот факт, что квадрат журнала совпадает, является совпадением   -  person Matt Timmermans    schedule 06.05.2020
comment
Совершенно моя точка зрения. Но этот вопрос был задан на моем экзамене по структурам данных, поэтому мне трудно понять removeMin () с max-heap.   -  person Hashir    schedule 06.05.2020

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

  • быть листом, или
  • иметь семерых детей,

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

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

person templatetypedef    schedule 06.05.2020
comment
Я сделал программу на C ++ для подсчета количества листовых узлов, но моя программа могла сосчитать только до 10 ^ 5 7-арного дерева. Точно не помню, но цифра была около 87 500. Разница между листовыми узлами и общим количеством узлов = 10 ^ 5 составляет около 12 500. Дерево узлов 10 ^ 6 также должно следовать тому же шаблону, поэтому как вы думаете, все же разумно выбрать 10 ^ 6, когда разница в тысячах узлов (сравнения). - person Hashir; 06.05.2020

arrow_upward
0
arrow_downward

Элемент 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.

Слева находится геометрический ряд, который в сумме составляет: (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 - массив для сортировки кучи.

person Hashir    schedule 06.05.2020