Какая сложность у операции heap push?

Операция вставки элемента в кучу (heap push) имеет временную сложность O(log n), где n — количество элементов в куче. Это связано с тем, что после добавления нового элемента в конец структуры, необходимо поднять его вверх по дереву (процедура "просеивания вверх" или sift-up), чтобы сохранить свойства кучи. Высота кучи примерно равна log n, поэтому операция занимает логарифмическое время.