Если добавлять каждую вершину в конец дерева, ее придется проталкивать вверх, а не вниз. Это невыгодно, так как сложность проталкивания вверх пропорциональна высоте уже построенного дерева, а вниз — высоте поддерева.
Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.
Простите, не вполне понял суть вопроса. Тем не менее, гарантия того, что обрабатываются вершины, имеющие потомков, — сама структура дерева. К тому же они не «поднимаются», а «опускаются».
Метод heapify вызывается только для поддеревьев, состоящих более чем из одного элемента. То есть для деревьев высоты 2, 3,…, H (пусть H=log2N — высота дерева), причем поддеревьев высоты k всего есть 2H-k.
heapify «жрет» не более O(log2N), а на самом деле O(h), где h — высота поддерева, для которого heapify вызывается. Тогда итоговая сложность упорядочения будет равна (k пробегает по всем значениям высот поддеревьев, которые нас интересуют)
причем 2H — это количество вершин в дереве, то есть N. А сумма
не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)
Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.
Метод heapify вызывается только для поддеревьев, состоящих более чем из одного элемента. То есть для деревьев высоты 2, 3,…, H (пусть H=log2N — высота дерева), причем поддеревьев высоты k всего есть 2H-k.
heapify «жрет» не более O(log2N), а на самом деле O(h), где h — высота поддерева, для которого heapify вызывается. Тогда итоговая сложность упорядочения будет равна (k пробегает по всем значениям высот поддеревьев, которые нас интересуют)
причем 2H — это количество вершин в дереве, то есть N. А сумма
не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)
Вы правы, я ошибся.