힙소트 intro
사실 제가 별도로 공부한 부분은 별로 없습니다. 정말 고마운 블로그 분들의 도움을 받아서 완전이진트리, 순서 조건 을 만족하는 자료구조가 힙이며 최대 힙이란 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 의미함을 파악할 수 있었습니다. 그리고 힙으로 숫자를 정렬하는 힙소트의 경우 최대힙 (혹은 최소힙) 을 미리 만든 상태에서 적용이 가능합니다. 제가 도움을 받은 블로그 링크를 첨부하겠습니다.
시간복잡도는 아직도 조금 햇갈립니다. 완전히 이해되는 날이 오겠…죠 ?
오늘 한 것 : 최대힙 만들기
저는 코딩 초보자이므로 일단 최대힙을 만들어야한다는데 이것 참… 쉽지 않았습니다. 어제 아르바이트 가기 전 + 아르바이트 갔다 온 후 + 오늘 아침 (낮잠을 자긴 했지만) 까지 낑낑대다가 만들 수 있었습니다. 사실 다른 방법들도 많이 검색할 수 있었지만 저는 Zedd0202님 블로그를 통해서 너무 명쾌하게 이해할 수 있었기에 Zedd0202님이 설명하신 방식대로 최대힙을 그대로 구현해보고 싶었습니다. Heap Sort 정렬 알고리즘
def MaxHeap(ar,i):
parent=i
print(parent,end='parent\n')
left_child=2*i
print(left_child,end='left_child\n')
if 2*i+1<=len(ar):
right_child=2*i+1
else:
right_child=None
print(right_child,end='right_child\n')
if left_child * 2 <= len(ar): #left_child에 자식이 있다면
MaxHeap(ar,left_child)
if right_child and right_child * 2 <= len(ar): #right_child에 자식이 있다면
MaxHeap(ar,right_child)
while parent*2<=len(ar):
if ar[left_child-1]<ar[right_child-1]:
big_child=right_child
elif ar[right_child-1]<ar[left_child-1]:
big_child=left_child
elif not right_child:
big_child=left_child
print(big_child,end='big_child\n')
if ar[parent-1]<ar[big_child-1]:
ar[parent-1],ar[big_child-1]=ar[big_child-1],ar[parent-1]
print(ar)
parent=big_child
left_child=parent*2
right_child=parent*2+1
print(parent,end='new parent\n')
print(left_child,end='new left\n')
print(right_child,end='new right\n')
MaxHeap([1,3,5,7,9,11,13,15,14,12,10,8,6,4,2],1)
이렇게 배열을 넣어보면
1parent
2left_child
3right_child
2parent
4left_child
5right_child
4parent
8left_child
9right_child
8big_child
[1, 3, 5, 15, 9, 11, 13, 7, 14, 12, 10, 8, 6, 4, 2]
8new parent
16new left
17new right
#child 인덱스가 너무 커져버려서 더이상 존재하지 않으므로 while 문 끝
5parent
10left_child
11right_child
10big_child
[1, 3, 5, 15, 12, 11, 13, 7, 14, 9, 10, 8, 6, 4, 2]
10new parent
20new left
21new right
#child 인덱스가 너무 커져버려서 더이상 존재하지 않으므로 while 문 끝
MaxHeap(ar,2) 에 걸려서 들어간 밑 재귀함수들이 반환됨으로써 부모노드가 2인 삼각형의 while 문이 돌아가게 됩니다.
4big_child
[1, 15, 5, 3, 12, 11, 13, 7, 14, 9, 10, 8, 6, 4, 2]
4new parent
8new left
9new right
9big_child
[1, 15, 5, 14, 12, 11, 13, 7, 3, 9, 10, 8, 6, 4, 2]
9new parent
18new left
19new right
#child 인덱스가 너무 커져버려서 더이상 존재하지 않으므로 while 문 끝
그리고 오른쪽 부분도 똑같은 방식으로 하여서 최종 최대힙이 만들어집니다
전체 출력 결과
1parent
2left_child
3right_child
2parent
4left_child
5right_child
4parent
8left_child
9right_child
8big_child
[1, 3, 5, 15, 9, 11, 13, 7, 14, 12, 10, 8, 6, 4, 2]
8new parent
16new left
17new right
5parent
10left_child
11right_child
10big_child
[1, 3, 5, 15, 12, 11, 13, 7, 14, 9, 10, 8, 6, 4, 2]
10new parent
20new left
21new right
4big_child
[1, 15, 5, 3, 12, 11, 13, 7, 14, 9, 10, 8, 6, 4, 2]
4new parent
8new left
9new right
9big_child
[1, 15, 5, 14, 12, 11, 13, 7, 3, 9, 10, 8, 6, 4, 2]
9new parent
18new left
19new right
3parent
6left_child
7right_child
6parent
12left_child
13right_child
12big_child
12new parent
24new left
25new right
7parent
14left_child
15right_child
14big_child
14new parent
28new left
29new right
7big_child
[1, 15, 13, 14, 12, 11, 5, 7, 3, 9, 10, 8, 6, 4, 2]
7new parent
14new left
15new right
14big_child
14new parent
28new left
29new right
2big_child
[15, 1, 13, 14, 12, 11, 5, 7, 3, 9, 10, 8, 6, 4, 2]
2new parent
4new left
5new right
4big_child
[15, 14, 13, 1, 12, 11, 5, 7, 3, 9, 10, 8, 6, 4, 2]
4new parent
8new left
9new right
8big_child
[15, 14, 13, 7, 12, 11, 5, 1, 3, 9, 10, 8, 6, 4, 2]
8new parent
16new left
17new right
출처를 반드시 주의해주세요
❗️코드 부분 이외의 모든 그림 설명 자료, 힙소트 설명 자료는 제가 제공하는 것이 하나도 없습니다. 제가 첨부한 링크를 꼭 확인해주세요 !