728x90

O(n*logn)의 성능을 나타내는 힙정렬을 파이썬으로 구현할 것이다.
필요한 지식
힙 (트리)
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위해 만든 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
힙을 이용하여 우선순위 큐를 구현하면 데이터를 삽입, 삭제하는데 log(n)의 시간이 걸린다.
종류
max heap :: 최대 힙
부모노드가 자식 노드보다 항상 큰 힙
EX.

min heap :: 최소 힙
부모노드가 자식 노드보다 항상 작은 힙
EX.

힙정렬
힙 트리 구조를 이용하는 정렬방법으로 병합정렬, 퀵정렬만큼 빠른 정렬 알고리즘이다.
최대 힙을 이용한 방법(상향식, 하향식)
1. 입력해오는 순서대로 혹은 배열의 순서대로 완전이진트리를 만들어준다

2. 완전이진트리를 구성하면 위에서부터(혹은 아래서부터) 각 노드들을 부모노드와 비교한다.

3. 만약 해당노드가 부모노드보다 크다면 부모노드와 해당노드를 교체해 준다.


4. 부모노드와 부모노드의 부모노드와도 부모노드가 자식노드보다 클 때까지 계속교체해 준다.

5. 이를 모든 노드에 대해 한다.
6. 최대 힙상태를 만들어주면 루트에는 제일 큰 값이 있다.

6. 완전이진 트리 잎노드의 마지막(9번 자리)을 루트로 옮긴다

7. 배열의 마지막 칸은 제일 큰 수로 고정되었으므로, 그 전까지의 배열로 위의 과정을 반복한다.





- 상향식은 위에서부터, 하향식은 아래서부터 노드들을 훑으며 내려오면 된다.
- 최소힙트리는 부모노드보다 자식노드를 크게 하면 최소힙트리가 만들어진다.
파이썬을 이용한 구현
num = int(input()) #정렬할 수의 개수를 입력받는다.
list = [] #빈 list를 생성한다.
for i in range(num):
list.append(int(input())) #빈 list에 정렬할 수를 입력받는다
for i in range(num):
for iii in range(1, num - i): #최대힙을 만드는 반복문이다.
ii = iii
while True: #부모 노드와 해당 노드의 비교를 하는 반복문이다.
parent = int((ii + ii % 2 - 2) / 2)
if list[parent] < list[ii]:
temp = list[parent]
list[parent] = list[ii]
list[ii] = temp
#만약 해당 노드가 부모 노드보다 더 크면 서로 교체해 준다.
else:
break
ii = parent #부모 노드와 그 부모 노드를 비교하기 위해 비교할 노드를 부모 노드로 봐꿔준다.
if ii == 0:
break
#만약 루트 노드까지 비교를 했다면 더 비교할 부모 노드가 없으므로 정지한다.
temp = list[num-i-1]
list[num-i-1] = list[0]
list[0] = temp
#루트 노드와 맨 마지막 잎 노드를 바꿔준 후 다음 반복문에서는 list의 마지막을 제외한 트리를 생성하도록 한다.
for n in list:
print(n)
참고자료 : velog.io/@humblechoi
반응형
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 모듈러 연산 (0) | 2023.10.15 |
|---|---|
| [알고리즘] 이항 계수 (0) | 2023.10.08 |
| [알고리즘] 소수 구하기 (아리토스테네스의 체) (0) | 2023.09.25 |
| [알고리즘] 최대공약수, 최소공배수 (유클리드 호제법) (0) | 2023.09.23 |
| [알고리즘] Merge sort :: 병합정렬 (1) | 2023.01.11 |