힙 정렬(Heap Sort)에서 공간 복잡도가 O(1)인 이유

힙 정렬의 기본 알고리즘은 다음과 같습니다.

 

1. 배열에 담긴 요소 중 가장 작은 값을 맨 뒤로 보내고,

그 값을 배열의 첫 번째 요소와 맞바꿉니다.

이렇게 되면 배열의 마지막에 위치했던 가장 작은 값이 맨 앞으로 오고, 

배열의 첫번째에 위치했던 요소는 맨 뒤로 가게 되겠죠.

2. 배열의 첫번째 요소를 배열에서 빼내고,

배열에 남아있는 요소들은 뒤섞습니다.

 

위 과정을 반복합니다.

 

예시를 통해 확인해 보겠습니다.

data:         1 4 7 2 5 8 9 3 6 0

make_heap:   [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right

pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap

pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap

etc

 

힙 정렬에서는 데이터가 어딘가에 따로 저장될 필요가 없습니다.

배열의 마지막 원소와 첫 번째 원소를 맞바꾸는 동안만 빼고요.

따라서 힙 정렬의 공간 복잡도는 O(1)입니다.

 

힙 정렬을 시각화 하면 다음과 같습니다.

make_heap 
           0
     2           1
  3     4     5     6
               8   7 9
pop_heap
           8                           1                           1
     2           1               2           8               2           5 
  3     4     5     6    ->   3     4     5     6    ->   3     4     8     6 
                   7 9                         7 9                         7 9

make_heap에서 맨 위에 위치한 0이 빠지고,

맨 아래 위치한 8이 마치 뛰어오르듯 

맨 위로 올라갑니다.

 

1과 8이 자리를 바꾸어

이번에는 1이 맨 위에 위치하고,

8은 1이 있던 자리로 내려갑니다.

 

5와 8이 자리를 바꾸어

8이 5가 있던 자리로 내려가고

5는 8이 있던 자리로 올라갑니다.