힙정렬(HeapSort) 이론과 파이썬 구현

힙정렬(HeapSort)

 

힙정렬은 리스트나 배열을 먼저 최소힙이나 최대힙으로 바꾸고 원소들을 순서대로 정렬하는 방법입니다.

최소힙은 최소값을 구할 때 사용하고 최대힙은 최대값을 구할때 이용합니다.

 

힙정렬은 완전 이진 트리입니다.

 

최소힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 형태의 완전 이진 트리

최대힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 형태의 완전 이진 트리

 

최소힙과 최대힙 예시

 

최대힙 만드는 과정

 

기존 리스트를 최대힙으로 바꾸는 과정입니다.

9의 위치를 찾기 위해 9와 2를 비교했을 때 9 > 2 이기 때문에 9와 2를 교환합니다.

9가 2의 위치로 오고 9와 5를 비교했을 때 9 >5 이기 때문에 9와 5를 교환합니다.

 

힙정렬을 이용한 정렬 과정

최대힙으로 만들고 원소들을 순서대로 정렬합니다.

루트에 있는 원소를 리스트 끝에서부터 넣어줍니다.

루트 값 9를 4와 교환하고 9는 정렬을 완료합니다. 그리고 4의 자리를 찾아줍니다.

4가 자리를 찾으며 루트에 새로운 값이 오게 되는데 이 값은 9를 제외하고 리스트에서 가장 큰 값입니다.

다음에는 이 값을 2와 교환하는 식으로 정렬 과정을 거칩니다.

 

힙정렬을 이용한 전체 정렬 과정

 

힙정렬의 파이썬 코드입니다.

def heap_sort(a):
    for i in range(1,len(a)): # 최대 힙 만들기
        c = i
        while c != 0:
            r = (c-1) // 2
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
                
            c = r

    for j in range(len(a)-1,-1,-1): # 힙 만들기
        a[0], a[j] = a[j], a[0]
        r = 0
        c = 1

        while c < j:
            c= 2 * r + 1
            if c < j -1 and a[c] < a[c+1]:
                c += 1
                
            if c < j and a[r] < a[c]:
                a[r], a[c]=a[c], a[r]
                
            r = c 

b = [5, 2, 3, 9, 6, 1, 8, 4, 7]
heap_sort(b)

# 결과>>[1, 2, 3, 4, 5, 6, 7, 8, 9]
print(b)