Pull to refresh
73
0
Ilya Khokhryakov @awolf

User

Send message
Есть же история изменений поста на SO. Сначала там вообще 16 было.
Спасибо за комментарии к статьям. Третью часть я тоже видел, но переводить пока что не планирую.
One V остается на ICS. HTC заявило, что устройства с 512MB или меньшим объемом памяти не будут обновляться до Jelly Bean. Вот здесь об этом написано:
In general, devices with 512MB RAM or less will not be upgraded to Android 4.1. At present, these devices include the HTC One V and the HTC Desire C.
Запускать с ключом --locale en:US
В общем-то да.
Если добавлять каждую вершину в конец дерева, ее придется проталкивать вверх, а не вниз. Это невыгодно, так как сложность проталкивания вверх пропорциональна высоте уже построенного дерева, а вниз — высоте поддерева.
Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.
Я уже отвечал на подобный вопрос.
Пожалуйста, инвайт на BitSpyder. Заранее спасибо.
Вы успокоитесь когда-нибудь со своим брейнфаком, а?
Везде, где обещают бесплатно выслать что-нибудь, 80% участников из России.
Тем не менее читать размазанный код с jpg — занятие не самое приятное.
Простите, не вполне понял суть вопроса. Тем не менее, гарантия того, что обрабатываются вершины, имеющие потомков, — сама структура дерева. К тому же они не «поднимаются», а «опускаются».
*алгоритма
Нет, нет отъедает:) Итак:

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

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

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

не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)
OH SHI~
Вы правы, я ошибся.
Точнее, метод heapify вызывается (log2N)/2 раз, что, впрочем, ничего не меняет.
1

Information

Rating
Does not participate
Registered
Activity