[긴급하다] 힙 정렬의 최악의 경우에 대해 질문이다

[힙정렬몰라요(175.192)]

알고리즘 중간고사를 앞두고 있는 학생이다.

힙 정렬에서 MAX-HEAPIFY 최악의 경우가 맨 밑의 트리가 반만 채워져 있을 경우라고 하던데

이것이 이해가 안된다 이말이다.

4시간 넘게 고민했는데 모르겠다.

도움을 요청한다.

[익명(223.33)]

힙정렬에 최악이있나?

[ㅅㅅㅅ(125.128)]

최악의 경우는 완전히 거꾸로 정렬되어 있는 경우지 뭐 다른 걸 생각할 게 있나. 완전히 거꾸로 정렬되어 있을 때는 항상 매 삽입 때마다 lgN번 작업 수행이 일어나니깐.