В CLRS, третьем издании, на стр. 155, указано, что в MAX-HEAPIFY,
"the worst case occurs when the bottom level of the tree is exactly half full"
Я предполагаю, что причина в том, что в этом случае Max-Heapify должен «плавать вниз» через левое поддерево.
Но я не мог понять, «почему наполовину заполнен»?
Max-Heapify также может плавать вниз, если левое поддерево имеет только один лист. Так почему бы не считать это худшим случаем?
Прочтите весь контекст:
Каждое дочернее дерево имеет размер не более 2n / 3 - худший случай возникает, когда последняя строка дерева заполнена ровно наполовину.
Поскольку время выполнения T(n) анализируется количеством элементов в дереве (n) и шагами рекурсии в одно из поддеревьев, нам нужно найти верхнюю границу количества узлов в поддереве относительно n, и что даст это T(n) = T(max num. nodes in subtree) + O(1)
Наихудший случай количества узлов в поддереве - это когда последняя строка максимально заполнена с одной стороны и максимально пуста с другой. Это называется наполовину полным. И размер левого поддерева будет ограничен 2n/3.
Если вы предлагаете вариант с несколькими узлами, это не имеет значения, поскольку все базовые варианты можно рассматривать O(1) и игнорировать.
T(n) = T(s(n)) + O(1), нам нужно найти наихудший случай для s(n) = subtree size as a function of n. Было бы неправильно сказать, что мы максимизируем размер поддерева (я видел это в паре других ответов, связанных с этим вопросом) - мы действительно максимизируем соотношение L/R, где L и R - это размер левого и правые поддеревья соответственно.
- person rmorshea; 10.10.2016
The worst case of number of nodes in a subtree is when the final row is as full as possible on one side, and as empty as possible on the other. Но почему? Я тоже точно сомневаюсь, как OP, Max-Heapify can also float down if left subtree has only one leaf. So why not consider this as the worst case ? Мне жаль, что это не ясно. Если возможно, очень поможет небольшое пояснение.
- person momo; 24.05.2018
Я знаю, что есть уже принятый ответ, но для тех, у кого такой же вопрос, но они все еще немного сбиты с толку (как и я), или что-то неясно - вот немного более длинное и подробное объяснение.
Хотя это может показаться скучным или излишним, мы должны очень четко указывать точные определения, потому что благодаря вниманию к деталям - есть вероятность, что когда вы это сделаете, доказать что-то станет намного проще.
Из раздела 6.1 CLRS, (двоичная) структура данных кучи - это объект массива, который мы можем рассматривать как почти полное двоичное дерево.
Из Википедии. В полном двоичном дереве все уровни, за исключением, возможно, последнего, полностью заполнены, а все узлы на последнем уровне находятся как можно дальше слева < / strong> насколько возможно.
Кроме того, из Википедии, сбалансированное двоичное дерево - это структура двоичного дерева, в которой левое и правое поддеревья каждого узла отличаются по высоте не более чем на 1.
Таким образом, по сравнению с корнем, высота левого и правого поддерева может отличаться максимум на 1.
Теперь рассмотрим дерево T, и пусть высота левого поддерева = h + 1, а высота правого поддерева = h
Какой наихудший случай в MAX_HEAPIFY? Худший случай - это когда мы в конечном итоге делаем больше сравнений и свопов, пытаясь сохранить свойство кучи.
Если алгоритм MAX_HEAPIFY работает и он рекурсивно проходит самый длинный путь, то мы можем рассмотреть возможный наихудший случай.
Что ж, все самые длинные пути находятся в левом поддереве (так как его высота h + 1). Почему не правильное поддерево? Запомните определение: все узлы на последнем уровне должны находиться как можно дальше слева.
Итак, чтобы получить большее количество самых длинных путей, мы должны сделать поддерево left ПОЛНЫМ (Почему? Чтобы у нас было больше путей для выбора, и мы выбрали путь, который дает наихудший случай. время). Поскольку левое поддерево имеет высоту h + 1, у него будет 2 ^ (h + 1) листовых узлов и, следовательно, 2 ^ (h + 1) самых длинных путей от корня. Это максимально возможное количество самых длинных путей в дереве T (высоты h + 1).
Вот изображение древовидной структуры в худшем случае.
Из приведенного выше изображения учтите, что желтое (слева) и розовое (справа) поддеревья имеют по x узлов каждое. Розовая часть - это полное правое поддерево, а желтая часть - это левое поддерево, за исключением последнего уровня.
Обратите внимание, что и желтое (слева), и розовое (справа) поддеревья имеют высоту h.
Теперь, с самого начала, мы считали, что левое поддерево имеет высоту h + 1 в целом (включая желтую часть и последний уровень), если я могу спросить, сколько узлов мы должны добавить в последний уровень, т.е. ниже желтой части, чтобы левое поддерево было полностью заполнено?
Итак, самый нижний слой желтой части имеет ⌈x / 2⌉ узлов (общее количество листьев в дереве / поддереве, имеющем n узлов = ⌈n / 2⌉; для проверочного посещения эта ссылка), и теперь, если мы добавим по 2 дочерних элемента к каждому из эти узлы / листья, = ›было добавлено всего x (≈x) узлов (как? ⌈x / 2⌉ оставляет * 2 ≈ узлов x).
С этим добавлением мы делаем левое поддерево высотой h + 1 (желтая часть с высотой h + добавленный последний уровень) и ПОЛНЫМ, следовательно, отвечающим критериям наихудшего случая.
Поскольку левое поддерево ПОЛНОЕ, все Дерево наполовину заполнено.
Теперь самый важный вопрос - почему бы нам не добавить больше узлов или не добавить узлы в правильное поддерево? Что ж, это потому, что теперь, если мы стремимся добавить больше узлов, узлы должны быть добавлены в правое поддерево (поскольку левое поддерево - ПОЛНОЕ), что, в свою очередь, будет иметь тенденцию больше уравновешивать дерево. . Теперь, когда дерево начинает становиться более сбалансированным, мы склоняемся к лучшему сценарию, а не к худшему.
Кроме того, сколько всего у нас узлов?
Общее количество узлов дерева n = x (из желтой части) + x (из розовой части) + x (добавление последнего уровня ниже желтой части) = 3x
Обратите внимание, что в качестве побочного продукта левое поддерево содержит не более 2x узлов, то есть 2n / 3 узлов (x = n / 3).
