똑똑한 코드 작성을 위한 실전 알고리즘

173

5

장

정렬

O

(

N

log

N

)의 성능을 달성하는 또 다른 방법은 각 단계의 런타임 성능이

O

(

log

N

)인

N

개 단

계로 구성하는 것이다. 다음 절에서 힙 자료구조를 사용해 성능이

O

(

N

log

N

)인 힙 정렬

Heap

Sort

을 다룬다.

5.8

힙 정렬

최대 이진 힙이 배열 정렬에 유용한 이유를 알아보자. [그림

5

-

13

]은 [그림

4

-

17

]의 힙에 대한

배열 저장 공간을 보여준다.

A

에서 가장 큰 값은

A

[

1

]

에 있다. 이 최댓값이 힙에서 꺼내어지면

기본 배열 저장 공간은 업데이트되어 값의 개수가 하나 적은 수정된 이진 힙을 반영한다. 더 중

요하게는, 인덱스 위치

A

[

18

]

은 사용되지 않을 뿐 아니라 배열이 정렬된다면 최댓값을 포함해

야 하는 인덱스 위치다. 단순히 힙에서 꺼낸 최댓값을 이 위치에 놓는다. 추가

dequeue

()

호출

후에 힙에서 두 번째로 큰 값은 이제는 사용되지 않을 인덱스 위치

A

[

17

]

에 들어갈 수 있다.

그림

5-13

최대 이진 힙을 사용해 정렬하기

레벨 0 레벨 1 레벨 2 레벨 3 레벨 4

가장 큰 값을 힙에서 꺼낸 후에

storage

배열이 업데이트된다. 마지막 인덱스 위치는 사용되지 않는다.

다시 가장 큰 값을 꺼낸다.

storage

배열이 업데이트되고 마지막 인덱스 위치는 사용되지 않는다.

174

똑똑한 코드 작성을 위한 실전 알고리즘 ...