[알고리즘] Heap sort :: 힙 정렬

 

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