Обсуждение:Биномиальная куча

Замечания

☐ Сделай у всех рисунков подписи, как у первого в конспекте.

☐ Почему пример merge горизонтальный, а extractMin - вертикальный?

☐ Рисунки, кажется, сделаны в WYSIWYG-редакторе:

☐ стрелки не отцентрированы

☐ впрочем, как и наложенные красные окружности

☐ и цифры внутри окружностей

☐ те отрезки, которые должны быть вертикальными, не вертикальны.

☐ на рисунке все центрировать или сделать горизонтальную большую стрелку

☐ и убрать точку слева от двойки в оранжевом прямоугольнике

☐ на рисунке фигурные скобки почему-то наклонены влево

☐ фигурная скобка справа, наверное, должна выделять все поддерево нуля

☐ Разнести левую и правую части рисунка, так чтобы они были слева и справа от стрелки.

Архив

☑ "то переход верный, то свойство доказано." исправить во всех утверждениях. Это касается и "То свойство доказано".

☑ На рисунке точка

☑ псевдокод не соответсвует требованиям

---

☑ ", в случае его минимальности относительно его родителя," — плохая формулировка

☑ "То для [math]i[/math] уровня" — в таких местах нужно добавлять окончание: "То для [math]i[/math]-го уровня" UPD не тире, а дефис (рекомендуется к прочтению)

☑ Исправить последнее утверждение.

☑ "То имеем асимптотику " - плохая формулировка

☑ В описании функции insert предложение несогласованно.

☑ Добавить категории. UPD Требования - Викификация - пункт 8

☑ Во всем конспекте время работы называется по-разному: "асимптотические оценки ", "общая асимптотика " - сделать однообразно. Не забывайте, что буквы O, o, Омега как раз означают, что время асимптотическое.

☑ Свойства оформить в виде утверждения. UPD Требования - Викификация - пункт 3

☑ "Удаление ключа сводится к двум предыдущим операциям: " - написать к каким именно, убрать слова "двум предыдущим".

☑ Исправить рисунок в примере к decreaseKey.

☑ Доказать, что delete работает за логарифм.

☑ Исправить названия процедур.

☑ Перерисовать все изображения.

☑ Переписать псевдокод по guideline.

☑ Исправить раздел "Источники". UPD: лишняя линия + Требования - Викификация - пункт 9 (смотрите Алгоритм Хаффмана и Сокращенная и минимальная ДНФ)

☑ Определение Биноминального дерева сделать не на всю ширину страницы (см. Шаблон: Определение). - поправил сам, теперь с версткой в этом месте все ОК.

☑ Картинку перенести вправо. Оформить как, например, в конспекте Дерево Уоллеса (с подписью).

☑ "Пример биномиального дерева для k = 0, 2, 3." -- "Пример биномиальных деревьев B_0, B_2 и B_3"

☑ Свойства биномиальных деревьев надо доказать.

☑ Все переменные занести в TeX (перечитайте Требования - TeX)

☑ Разбить конспект на части, используя заголовки разных уровней.

☑ Убрать лишнюю линию после заголовка "Операции над биномиальными пирамидами"

☑ Из "Определение: Биномиальная пирамида" убрать символ 'H'.

☑ После " следующим свойствам биномиальных пирамид." должна быть не точка, а двоеточие

☑ В предложении " следующим свойствам биномиальных пирамид." убрать "биномиальных пирамид"

☑ makeHeap -- убрать, не несет смысла

☑ В функции delete минус бесконечность

☑ head[H] - head это не массив. Оставьте просто head, без скобок

☑ Требования - Викификация - пункт 5

☑ "Асимптотика этой операции получается из того" - ужасное предложение, переписать. Асимптотика ниоткуда не получается.

☑ Сокращать слова нельзя.

☑ "В силу того, что с увеличением порядка дерева на количество узлов увеличивается вдвое, а изначально дерево имеет узел, то при любом , дерево порядка имеет узлов." - плохое предложение. Нужно написать "Так как в дереве порядка k+1 вдвое больше узлов, чем в дереве порядка k, а в дереве нулевого порядка 1 = 2^0 узел, то дерево порядка k имеет 2^k узлов" UDP аналогичные предложения исправить в других свойствах.

☑ Найти место и добавить туда ссылку на конспект про кучу. Переставить ссылку.

---

☐ Оценки времени работы. В Кормене даны оценки для наихудшего случая.

☑ Перерисовать картинку для merge:

1. Нужно разделить два случая и подписи на стрелочках перенести в подписи к изображениям.
   • В принципе достаточно одного случая, а тексте написать, что иначе подвешиваем их наоборот.
2. Несогласованны обозначения: вместо key[x] нужно x.key
3. Плохо, когда две одинаковые буквы обозначают разные вещи : x и X. В частности, как и в пункте 2, для степени есть обозначения x.degree
4. x лучше переименовать в current
5. сказать о том, что степени узлов равны можно так : b.degree = c.degree
   • Обозначение Y не нужно
6. x.next и x.prev можно убрать -- и так понятно, что это список
   • офф-топик: от предыдущих версий осталась черточка после prev, а точка (между x и prev/next) слишком выделяется
7. то, что выделено фигурными скобками можно будет обозначить так [math]c'.degree = c.degree + 1[/math]

☑ Словесное описание функции decreaseKey UPD: не нужно описание писать в будущем времени. UPD2: теперь еще хуже

• Плохо начиная со слов "... то есть алгоритм состоит в том, что если ...". Можно убрать все после слова "всплывает" до "Процедура выполняется за время". И добавить, что вершина всплывает, как в обычной куче.

☑ В decreaseKey глубина вершины в общем случае - O(log n). Нужно либо указать, что это худший случай, либо исправить.

☑ Путаница next prev sibling. Список корней -- односвязный. В Кормене обозначение для полей в узле это массивы: x.sibling = sibling[x], а next-x - это название переменной. Поэтому нужно убрать упоминания x.next и x.prev, оставив только x.sibling.