사전 조건
- 배열이 완전 이진 트리 구조여야 한다.
(완전 이진 트리 - Complete binary tree :
각각의 노드가 최대 2개 씩의 자식 노드를 가진 이진 트리 구조에서
root 노드의 왼쪽부터 자식 노드를 차례로 삽입하는 트리 구조를 말한다.)
종류
- 최대 힙 (부모 노드가 자식 노드보다 큰 힙)
- 최소 힙 (부모 노드가 자식 노드보자 작은 힙)
용어
- leaf 노드 : 자식 노드가 없는 노드들
- 힙 생성 알고리즘 (heapify) : 부모 노드와 자식 노드들 중에서 값이 가장 큰 값을 부모 노드로 변경 해주는 작업
- 상향식 : 아래 노드에서 위로 올라가는 작업
- 하향식 : 위에 노드부터 아래로 내려가는 작업
(상향식과 하양식은 편한대로 구성한다. 저자는 상향식으로 구성했다.)
동작 방식
- 10개의 값이 있다고 가정하면 heapify작업을 하는 list의 index 값의 순서는 아래와 같다.
index : [자식노드 : 왼쪽 값] [부모노드] [자식노드 오른쪽 값]
index : 9 4
index : 7 3 8
index : 5 2 6
index : 3 1 4
index : 1 0 2
- 상단에 index 값 중에서 가장 큰 값을 가운데 부모 노드에 저장한다.
- 해당 작업을 전체 노드 수의 1/2 만큼만 진행한다.(leaf 노드를 제외하고 진행하기 때문)
- 작업이 끝나면 첫번째 값이 가장 큰 값이 되므로 가장 마지막 값과 자리를 바꾼다.
- 위 작업을 list의 작업 범위를 줄여가며 진행한다.
0 ~9 작업 후 0 의 값을 9에 넣기
0 ~8 작업 후 0 의 값을 8에 넣기
ex) 배열 값 예시
[7, 4, 5, 8, 9, 3, 2, 1, 6, 10]
[6, 7, 5, 8, 4, 3, 2, 1, 9, 10]
[1, 6, 5, 7, 4, 3, 2, 8, 9, 10]
[2, 1, 5, 6, 4, 3, 7, 8, 9, 10]
[3, 2, 5, 1, 4, 6, 7, 8, 9, 10]
[2, 4, 3, 1, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
장점
- 퀵 정렬보다 안정적으로O(NlogN)을 보장한다.
- 메모리 상으로는 병합정렬 보다 효율적이다.
시간 복잡도
O(NlogN)
- 힙 생성 알고리즘(heapify)작업에 걸리는 시간 복잡도는 완전 이진 트리 구조이기 때문에 로그2에 N 이다.
- (1/2)n개의 정점에 대해서 진행하기 때문에 (1/2)n* 로그2에 N이다. 따라서 사실상 O(n)가까운 속도가 된다.
- 그러나 공식적인 알고리즙의 시간 복잡도는 [힙 생성 알고리즘을 만드는데 걸리는 시간 logN] * [전체 데이터의 갯수 N]
- 따라서 O(NlogN)이 된다.
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 27
@ Update : 2020. 01. 27
@ Description : Heap sort (힙 정렬)
'''
def fn_swapping(list_target, int_index_a, int_index_b):
'''
@Description: List index swapping
@Arguments Example
list_target = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
int_index_a = 0
int_index_b = 2
'''
value_tmp = list_target[int_index_a]
list_target[int_index_a] = list_target[int_index_b]
list_target[int_index_b] = value_tmp
return list_target
def fn_heap_sort(list_input):
'''
@Description: Heap sort (힙 정렬)
@Arguments Example
list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
'''
int_len_list_input = len(list_input)
for int_main_index in reversed(range(2, int_len_list_input + 1)):
int_range = int_main_index//2
if int_main_index%2 == 0:
if list_input[int_range*2 - 1] > list_input[int_range - 1]:
list_input = fn_swapping(list_input, int_range*2 - 1, int_range - 1)
int_range -= 1
for int_index in reversed(range(1, int_range + 1)):
if list_input[int_index*2 - 1] > list_input[(int_index*2)]:
if list_input[int_index*2 - 1] > list_input[int_index - 1]:
list_input = fn_swapping(list_input, int_index*2 - 1, int_index - 1)
else:
if list_input[int_index*2] > list_input[int_index - 1]:
list_input = fn_swapping(list_input, int_index*2, int_index - 1)
print(" index : ", int_index*2 - 1, int_index - 1, int_index*2)
list_input = fn_swapping(list_input, 0, int_main_index - 1)
return list_input
if __name__ == "__main__":
list_fn_heap_sort_param = [1, 9, 5, 4, 7, 3, 2, 8, 6, 10]
print(fn_heap_sort(list_fn_heap_sort_param))