시간복잡도 관련 보충 링크
힙소트 1 에서 만든 최대힙의 시간복잡도가 왜 O(N) 인지 잘 이해가 안 갔었는데 다음의 블로그를 통해 도움을 받았습니다. 😀 링크를 첨부합니다.
O(N) : 최대힙 만들기 + O(N*logN) : 루트노드 지우면서 다운힙 이므로 힙소트의 시간복잡도는
O(NlogN) 이라고 할 수 있습니다.
최종 코드
최대힙 만들기, 루트 노드 지워가면서 다운힙 과정을 모두 합친 코드입니다. 지난 번 코드에서 조금의 문제점을 발견해서 그 부분도 같이 수정하였습니다.
import sys
class HeapSortTotal:
def read(self):
self.ar=list(map(int,sys.stdin.readline().split()))
def MaxHeap(self,i):
parent=i
print(parent,end='parent\n')
left_child=2*i
print(left_child,end='left_child\n')
if 2*i+1<=len(self.ar):
right_child=2*i+1
else:
right_child=None
print(right_child,end='right_child\n')
if left_child * 2 <= len(self.ar): #left_child에 자식이 있다면
self.MaxHeap(left_child)
if right_child and right_child * 2 <= len(self.ar): #right_child에 자식이 있다면
self.MaxHeap(right_child)
while parent*2<=len(self.ar):
if right_child:
if self.ar[left_child-1]<self.ar[right_child-1]:
big_child=right_child
else:
big_child=left_child
else:
big_child=left_child
print(big_child,end='big_child\n')
if self.ar[parent-1]<self.ar[big_child-1]:
self.ar[parent-1],self.ar[big_child-1]=self.ar[big_child-1],self.ar[parent-1]
print(self.ar)
parent=big_child
left_child=parent*2
if 2*parent+1<=len(self.ar):
right_child=2*parent+1
else:
right_child=None
print(parent,end='new parent\n')
print(left_child,end='new left\n')
print(right_child,end='new right\n')
def HeapSort(self):
#최대힙 array
final_sort=[]
num=len(self.ar)
while len(final_sort)<num:
self.ar[-1],self.ar[0]=self.ar[0],self.ar[-1]
print(self.ar)
final_sort.insert(0,self.ar[-1])
print(final_sort)
del self.ar[-1]
print(self.ar)
parent=1
left_child=2
if len(self.ar)>2:
right_child=3
else:
right_child=None
while parent*2<=len(self.ar):
if right_child:
if self.ar[left_child-1]<self.ar[right_child-1]:
big_child=right_child
else:
big_child=left_child
else:
big_child=left_child
print(big_child,end='big_child\n')
if self.ar[parent-1]<self.ar[big_child-1]:
self.ar[parent-1],self.ar[big_child-1]=self.ar[big_child-1],self.ar[parent-1]
print(self.ar)
parent=big_child
left_child=parent*2
if 2*parent+1<=len(self.ar):
right_child=2*parent+1
else:
right_child=None
print(parent,end='new parent\n')
print(left_child,end='new left\n')
print(right_child,end='new right\n')
letsheap=HeapSortTotal()
letsheap.read()
letsheap.MaxHeap(1)
print('-------------')
letsheap.HeapSort()
출력 결과
1 3 5 7 9 11 13 15 14 12 10 8 6 4 2 #터미널에서 해당 숫자들을 넣어줬습니다.
# 출력 결과 :
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
Nonenew 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
Nonenew 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
Nonenew right
3parent
6left_child
7right_child
6parent
12left_child
13right_child
12big_child
12new parent
24new left
Nonenew right
7parent
14left_child
15right_child
14big_child
14new parent
28new left
Nonenew 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
Nonenew 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
Nonenew right
-------------
[2, 14, 13, 7, 12, 11, 5, 1, 3, 9, 10, 8, 6, 4, 15]
[15]
[2, 14, 13, 7, 12, 11, 5, 1, 3, 9, 10, 8, 6, 4]
[14, 2, 13, 7, 12, 11, 5, 1, 3, 9, 10, 8, 6, 4]
2new parent
4new left
5new right
[14, 12, 13, 7, 2, 11, 5, 1, 3, 9, 10, 8, 6, 4]
5new parent
10new left
11new right
[14, 12, 13, 7, 10, 11, 5, 1, 3, 9, 2, 8, 6, 4]
11new parent
22new left
Nonenew right
[4, 12, 13, 7, 10, 11, 5, 1, 3, 9, 2, 8, 6, 14]
[14, 15]
[4, 12, 13, 7, 10, 11, 5, 1, 3, 9, 2, 8, 6]
[13, 12, 4, 7, 10, 11, 5, 1, 3, 9, 2, 8, 6]
3new parent
6new left
7new right
[13, 12, 11, 7, 10, 4, 5, 1, 3, 9, 2, 8, 6]
6new parent
12new left
13new right
[13, 12, 11, 7, 10, 8, 5, 1, 3, 9, 2, 4, 6]
12new parent
24new left
Nonenew right
[6, 12, 11, 7, 10, 8, 5, 1, 3, 9, 2, 4, 13]
[13, 14, 15]
[6, 12, 11, 7, 10, 8, 5, 1, 3, 9, 2, 4]
[12, 6, 11, 7, 10, 8, 5, 1, 3, 9, 2, 4]
2new parent
4new left
5new right
[12, 10, 11, 7, 6, 8, 5, 1, 3, 9, 2, 4]
5new parent
10new left
11new right
[12, 10, 11, 7, 9, 8, 5, 1, 3, 6, 2, 4]
10new parent
20new left
Nonenew right
[4, 10, 11, 7, 9, 8, 5, 1, 3, 6, 2, 12]
[12, 13, 14, 15]
[4, 10, 11, 7, 9, 8, 5, 1, 3, 6, 2]
[11, 10, 4, 7, 9, 8, 5, 1, 3, 6, 2]
3new parent
6new left
7new right
[11, 10, 8, 7, 9, 4, 5, 1, 3, 6, 2]
6new parent
12new left
Nonenew right
[2, 10, 8, 7, 9, 4, 5, 1, 3, 6, 11]
[11, 12, 13, 14, 15]
[2, 10, 8, 7, 9, 4, 5, 1, 3, 6]
[10, 2, 8, 7, 9, 4, 5, 1, 3, 6]
2new parent
4new left
5new right
[10, 9, 8, 7, 2, 4, 5, 1, 3, 6]
5new parent
10new left
Nonenew right
10big_child
[10, 9, 8, 7, 6, 4, 5, 1, 3, 2]
10new parent
20new left
Nonenew right
[2, 9, 8, 7, 6, 4, 5, 1, 3, 10]
[10, 11, 12, 13, 14, 15]
[2, 9, 8, 7, 6, 4, 5, 1, 3]
[9, 2, 8, 7, 6, 4, 5, 1, 3]
2new parent
4new left
5new right
[9, 7, 8, 2, 6, 4, 5, 1, 3]
4new parent
8new left
9new right
[9, 7, 8, 3, 6, 4, 5, 1, 2]
9new parent
18new left
Nonenew right
[2, 7, 8, 3, 6, 4, 5, 1, 9]
[9, 10, 11, 12, 13, 14, 15]
[2, 7, 8, 3, 6, 4, 5, 1]
[8, 7, 2, 3, 6, 4, 5, 1]
3new parent
6new left
7new right
[8, 7, 5, 3, 6, 4, 2, 1]
7new parent
14new left
Nonenew right
[1, 7, 5, 3, 6, 4, 2, 8]
[8, 9, 10, 11, 12, 13, 14, 15]
[1, 7, 5, 3, 6, 4, 2]
[7, 1, 5, 3, 6, 4, 2]
2new parent
4new left
5new right
[7, 6, 5, 3, 1, 4, 2]
5new parent
10new left
Nonenew right
[2, 6, 5, 3, 1, 4, 7]
[7, 8, 9, 10, 11, 12, 13, 14, 15]
[2, 6, 5, 3, 1, 4]
[6, 2, 5, 3, 1, 4]
2new parent
4new left
5new right
[6, 3, 5, 2, 1, 4]
4new parent
8new left
Nonenew right
[4, 3, 5, 2, 1, 6]
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[4, 3, 5, 2, 1]
[5, 3, 4, 2, 1]
3new parent
6new left
Nonenew right
[1, 3, 4, 2, 5]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 3, 4, 2]
[4, 3, 1, 2]
3new parent
6new left
Nonenew right
[2, 3, 1, 4]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[2, 3, 1]
[3, 2, 1]
2new parent
4new left
Nonenew right
[1, 2, 3]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 2]
2big_child
[2, 1]
2new parent
4new left
Nonenew right
[1, 2]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1]
[1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] #제대로 정렬되었습니다
[]
비주얼스튜디오 🤩
드디어 비주얼스튜디오를 깔았습니다 ! 이 코드도 다 비주얼스튜디오에서 작성하였습니다.
코드 치기도 너무 좋고 가독성 있어서 너무 마음에 듭니다 :)