힙 정렬을 공부하면서 개인적으로 헷갈렸던 부분이
Heap을 만드는 부분 그리고 Heap이 완성되었을 때 정렬하는 부분이 나눠져 있는 부분이었다. 더불어 heap sort 를 공부할 때에는 많은 용어들이 나와서 조금 더 복잡하게 느껴졌던 것 같다.
1. Heap 만들기
heap을 만드는데에는 여러가지 구현 방법이 있다.
내가 사용할 방법은 이진힙(Binary heap)이다.
우선 힙의 특성을 먼저 살펴보자면
부모의 값이 자식의 값보다 항상 크거나 작은 조건을 만족하는 완전 이진 트리 라는 점이다.
풀어서 이야기하면
부모 노드는 항상 자식 노드들 보다 값이 작거나 커야하고, 트리의 마지막 레벨은 제외하고 모든 노드가 채워져있어야하고, 마지막 레벨은 꽉 차있지 않아도 되지만 왼쪽 에서 오르쪽 방향으로 노트가 채워져있어야 한다.
여기서 heap 트리를 생성하는 알고리즘을 heapify라 부른다.
그러면 어떠한 배열이 주어졌을 때, heapify 를 어떻게 할까?
heap 을 만들거면 먼저 정해야 하는 점이 있다.
Max heap 을 만들지, Min heap 을 만들지이다.
Max heap : 부모노드의 값이 자식노드의 값보다 큼 ( 부모 > 자식 )
Min heap : 부모노드의 값이 자식노드의 값보다 작음 ( 부모 < 자식 )
Min heap 을 만든다고 생각하고 진행해보겠다.
다음과 같이 배열이 주어졌다.
arr = [ 7, 3, 10, 2, 1, 13 ]여기서 우리가 생각해야 되는 점은 부모 노드가 자식 노드보다 작아야 된다는 점이다.
해당 배열을 트리로 그려보면 아래와 같다.
여기서 우리는 가장 마지막 부모 노드 부터 확인하여, 부모 노드가 자식 노드보다 작은지 확인 할 것이다.
# 가장 마지막에 위치한 부모의 노드 확인 하는 법
(배열의 길이 // 2 ) - 1
for i in range(len(arr) // 2 -1, -1, -1) :
heapify(arr,len(arr),i)위에 코드는 가장 마지막에 위치한 부모의 노드부터 순차적으로 확인한다는 의미이다.
그러면 주어진 배열로 생각해보면 i = 2 부터 시작한다. 즉 arr[2] 인 값인 10을 부모로 잡고 자식노드와 값을 비교할 것이다.
for i in range(len(arr) // 2 -1, -1, -1) :
heapify(arr,len(arr),i)def heapify(arr, n,i):
# 부모 인덱스 값을 부모에 넣어줌
parent = i
# 부모의 왼쪽 자식을 계산하는 법
left = 2 * i + 1
# 부모의 오른쪽 자식을 계산하는 법
right = left + 1
# left < n 은 총 배열의 갯수보다 left 값이 작으면, 존재한다는 의미이고
# 부모의 값이 왼쪽 자식의 값보다 크면, 부모 값에 왼쪽자식 인덱스 값을 넣는다.
if left < n and arr[parent] > arr[left] :
parent = left
# right < n 은 총 배열의 갯수보다 right 값이 작으면, 존재한다는 의미이고
# 부모의 값이 오른쪽 자식의 값보다 크면, 부모 값에 오른쪽 자식 인덱스 값을 넣는다.
if right < n and arr[parent] < arr[right]:
parent = right
# 그리고 원래 처음 주어진 부모의 인덱스와 현재 담겨있는 부모의 인덱스 값이 다르면,
# 부모가 자식들보다 큰 값을 들고 있었다는 이야기이고, 작은 값으로 바꿔줘야 한다.
# 그리고 새로운 부모가 생겼으니, 그 부모를 기준으로 다시 heapify 를 해준다.
if parent != i:
arr[i], arr[parent] = arr[parent], arr[i]
heapify(arr, n, parent) 
마지막 부모인 노드 arr[2]인 10을 자식과 비교한다.
(위에 heapify 함수를 기반으로 힙을 만든다. 참고하여 확인)
parent = 2
left = 5
right = 6
arr[2] = 10은 왼쪽 자식인 13과 비교했을 때 작으니까 그대로 두고
오른쪽 노드는 없어서 비교할 필요가 없고 다음 부모를 찾는다.
다음 부모 노드는 arr[1] 이다
parent = 1
left = 3
right = 4
arr[1] 는 값이 3이고, 3은 왼쪽 자식 arr[3]의 값인 2보다 크다.
그래서 parent = 3 을 넣어준다.
(다시 말하지만 우린 부모 < 자식 이 성립해야 된다.)
그리고 현재 parent인 arr[3] 값 2와 오른쪽 자식 arr[4] 값인 1과 비교해서 1이 작기 때문에 parent = 4 를 넣어준다.
그리고 실제로 parent 값인 1과 4는 값이 다르기 때문에, 서로 자리를 바꿔준다.
그리고 값이 변경되었기 때문에, 변경되기 전에 만족했던 힙 구조가 영향을 받을 수 있다. 그래서 heapify 를 한번 더 해준다! 여기서는 문제가 없어서 넘어간다.
이제 마지막 최종 부모의 값을 확인할 차례이다.
parent = 0
left = 1
right = 2
arr[0] 의 값인 7 은 왼쪽자식 arr[1] 보다 크다.
parent = 1
새로운 parent 값인 arr[1] 의 값은 arr[2] 보다 작으니 그대로 둔다.
그리고 맨 처음 parent 값인 0 과 새로운 값인 1은 다르기 때문에 서로 위치를 바꿔준다.
그리고 값이 변경되었으니 arr[1] 7이 왼쪽 오른쪽 자식들보다 여전히 작은지 확인해야한다. 그래서 다시 한번 heapify 한다.
parent = 1
left = 3
right = 4
좀 축약해서 적으면 왼쪽 자식이 제일 작다. 그래서 arr[1] 와 arr[3]을 서로 바꿔준다.
이로써 모든 힙을 구성했다.
여기까지가 부모가 자식들보다 작은 값을 가지고 있는 Min-heap 이다.
Max-heap 을 만들고 싶으면, heapify 코드에서 부등호 방향만 반대로 해주면된다.
2. Heap sort
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)이제 완벽한 힙이 만들어졌으면 Heap 정렬을 할 수 있다.
나는 내림차순으로 정렬하고 싶다.
우선 root에 있는 값은 항상 모든 원소 중에서 가장 작은 수이다.
그래서 해당 root 를 배열의 끝으로 보내고, 가장 마지막 노드에 있는 값을 root로 보낸다.
그리고 이제 마지막으로 보낸 값은 더 이상 정렬하지 않는다.
잘 보면 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
그래서 우선순위 큐라 부른다.
그러면 이제 root 가 13으로 변경되었으니 힙 구조가 망가졌을 수 있다. 그러디까 heapify 해준다.
그러면 이번에는 13과 2을 바꿔준다.
그러면 2는 정렬이 완료되고 건드리지 않는다. 그리고 13을 또 heapify~ 한다.
그리고 또 3과 13을 바꾸고 heapify!
7과 10을 바꾸고 heapify!
10과 13 바꾸고 정렬 끝!
이렇게 정렬하면 heap sort 가 끝난다.
시간의 복잡도
힙 구조 생성시 연산 수는 힙의 높이와 동일하므로 O(log N)이 됩니다.
따라서 힙 정렬의 전체 시간 복잡도는 힙 생성(Heapify)알고리즘 시간 복잡도 O(log N) 전체 데이터 수 N = O(N logN)입니다.
