배열을 최대 힙으로 만든 뒤, 맨 위의 가장 큰 값을 맨 뒤로 보내고 남은 부분을 다시 힙으로 고치는 일을 반복합니다. 트리를 따로 만들지 않고 배열 안에서 부모와 자식의 위치를 계산해 씁니다.

힙 정렬 과정을 막대와 트리로 함께 보여 주는 시뮬레이터

[자동 재생]을 누르거나 [다음 단계]로 한 단계씩 넘겨 보세요. 슬라이더를 끌면 원하는 단계로 바로 이동합니다. 아래 트리 그림은 위 막대와 같은 배열을 트리 모양으로 다시 그린 것입니다.

최선O(n log n)

평균O(n log n)

최악O(n log n)

추가 공간O(1)

안정 정렬아니요

힙 만들기O(n)

배열이 곧 트리입니다

i번 노드의 왼쪽 자식은 2i+1번, 오른쪽 자식은 2i+2번, 부모는 (i−1)//2번입니다. sift_down은 부모가 더 큰 자식보다 작으면 둘을 바꾸며 아래로 내려가는 연산입니다. 트리 높이만큼만 내려가므로 O(log n)이고, 이것을 n번 하므로 전체는 O(n log n)입니다.

처음 힙을 만들 때는 자식이 있는 마지막 노드부터 거꾸로 sift_down 합니다. 아래쪽 노드는 내려갈 거리가 짧아서, 합쳐 보면 O(n log n)이 아니라 O(n)에 끝납니다.

코테에서는: 힙은 정렬보다 우선순위 큐로

힙 정렬을 직접 짤 일보다 힙을 우선순위 큐로 쓸 일이 훨씬 많습니다. 파이썬 heapq는 최소 힙이라서, 최대 힙이 필요하면 값에 −를 붙여 넣습니다. 가장 큰 k개는 크기 k인 최소 힙을 유지하면 O(n log k)에 구합니다.

import heapq
h = []
for x in a:
    heapq.heappush(h, x)
    if len(h) > k:
        heapq.heappop(h)    # 힙에서 가장 작은 값을 버림
# h에 가장 큰 k개가 남음