Нижняя граница для heapsort?

Хорошо известно, что наихудшее время выполнения для heapsort - Ω (n lg n), но Мне трудно понять, почему это так. В частности, первый шаг psort (создание максимальной кучи) требует времени Θ (n). Затем следует n удалений кучи. Я понимаю, почему каждое удаление кучи занимает время O (lg n); перебалансировка кучи включает в себя операцию «пузырька вниз», которая занимает время O (h) по высоте кучи, а h = O (lg n). Однако я не понимаю, почему этот второй шаг должен занять Ω (n lg n). Кажется, что любое удаление из очереди отдельной кучи не обязательно приведет к перемещению узла наверх, чтобы пузыриться вниз по дереву.

Мой вопрос - знает ли кто-нибудь о хорошем нижнем доказательстве наилучшего поведения heapsort?