awolf
+3
Есть же история изменений поста на SO. Сначала там вообще 16 было.
awolf
+2
Спасибо за комментарии к статьям. Третью часть я тоже видел, но переводить пока что не планирую.
awolf
+6
Запускать с ключом --locale en:US
awolf
0
В общем-то да.
awolf
0
Если добавлять каждую вершину в конец дерева, ее придется проталкивать вверх, а не вниз. Это невыгодно, так как сложность проталкивания вверх пропорциональна высоте уже построенного дерева, а вниз — высоте поддерева.
Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.
awolf
0
Я уже отвечал на подобный вопрос.
awolf
0
Пожалуйста, инвайт на BitSpyder. Заранее спасибо.
awolf
+5
Пробовал.
awolf
+1
ИХ
awolf
+2
ИХ
awolf
+6
Вы успокоитесь когда-нибудь со своим брейнфаком, а?
awolf
+44
Везде, где обещают бесплатно выслать что-нибудь, 80% участников из России.
awolf
+6
Тем не менее читать размазанный код с jpg — занятие не самое приятное.
awolf
0
Простите, не вполне понял суть вопроса. Тем не менее, гарантия того, что обрабатываются вершины, имеющие потомков, — сама структура дерева. К тому же они не «поднимаются», а «опускаются».
awolf
0
*алгоритма
awolf
+2
Нет, нет отъедает:) Итак:

Метод heapify вызывается только для поддеревьев, состоящих более чем из одного элемента. То есть для деревьев высоты 2, 3,…, H (пусть H=log2N — высота дерева), причем поддеревьев высоты k всего есть 2H-k.

heapify «жрет» не более O(log2N), а на самом деле O(h), где h — высота поддерева, для которого heapify вызывается. Тогда итоговая сложность упорядочения будет равна (k пробегает по всем значениям высот поддеревьев, которые нас интересуют)

причем 2H — это количество вершин в дереве, то есть N. А сумма

не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)
awolf
0
OH SHI~
Вы правы, я ошибся.
awolf
0
Точнее, метод heapify вызывается (log2N)/2 раз, что, впрочем, ничего не меняет.
awolf
+1
O(n) требуется, чтобы построить дерево, не обращая внимание на соблюдение основного свойства кучи. Чтобы упорядочить binaryHeap, log2N раз вызываем метод heapify, сложность которого O(log2N), то есть процесс упорядочения более быстр. Поэтому итоговая оценка O(n).
awolf
+1
Например, там, где нужно быстро извлекать максимальный/минимальный элемент. Уже упомянутый алгоритм Дейкстры с хипом и, думаю, другие алгоритмы на графах. Еще, например, выбор m максимальных/минимальных элементов из массива.
awolf
0
Про heapSort, собственно, я в статье написал.
awolf
+3
Простите, но первая картинка вырвиглазна.
awolf
+2
Хм. Звучит все это заманчиво.
awolf
+3
Если бы было указано, что это первая часть, было бы лучше. А вообще, мне кажется, начало довольно интересное (для кодера, который редко держит в руках паяльник).
awolf
+2
Пост может заставить кого-нибудь наконец «навести порядок», и не только в почте. А это хорошо.
awolf
–1
Как вебодиннольненько-то.
awolf
+1
И по запросу «календарь.рф» эта статья на Хабре выпадает раньше, чем сам сайт.