[알고리즘] 힙정렬

Hyo Kyun Lee·2022년 1월 12일

heap 알고리즘 힙 힙정렬

알고리즘

목록 보기

7/45

6. 힙정렬

heap 구조를 이용하여 data를 정렬하는 방법으로, 병합/퀵정렬과 마찬가지로 시간복잡도가 O(N*logN)을 가지는 방법이다.

6-1. 이진트리

Binary Tree, 컴퓨터가 데이터를 표현할 때 데이터를 각 노드에 담은 후 해당 노드들을 이어붙이는 구조를 말하며, 부모노드에 대한 자식노드가 2개 이하이다.

보통 부모노드를 Root, 자식노드를 Leaf라 일컫는다.

6-2. 완전이진트리

Complete Binary Tree, 데이터가 이진트리구조로 정렬되면서 노드를 중간에 비지않고 왼쪽노드부터 오른쪽노드까지 차근차근 삽입되는 구조를 말한다.

보통 이진트리구조에서 부모노드들이 모두 빠짐없이 들어가있고, 자식노드들이 왼쪽부터 들어가있는 구조를 말한다.

6-3. Heap

완전이진트리구조에서 데이터를 상향 및 하향식으로 구성하여, 최대값, 최소값을 빠르게 찾아내기 위해 구조화한 구조를 말한다.

부모노드부터 자식노드까지 최대값순으로(내림차순) 구성되어있다면 max heap, 최소값순으로(오름차순) 구성되어있다면 min heap이라 한다.

6-4. heapify algorithm

힙생성 알고리즘은 이러한 heap정렬, 즉 heap을 구성하는 알고리즘을 의미한다.

보통 max, min heap 조건에 맞게 노드들을 탐색하고, 조건에 맞지 않은 노드가 발견되면 해당 노드에 대해 힙생성 알고리즘을 수행한다.

즉 특정 노드(부모)와 해당 자식 노드를 비교하여 자식과 위치를 바꾸고, 위치를 바꾼 이후 자식을 부모 노드로 하여 하단 구조가 heap과 부합하는지 탐색한다.

6-5. 파이썬 코드

heap 정렬은 크게 두가지로 구현할 수 있다.

데이터를 배열에 삽입하고, heap구조에 맞게 재정렬한다(max or min).
heap 구조를 다시 reverse(상향 or 하향식)하여 재배열한다.

※ heap구조를 재배열하는 경우엔 최상단 노드에 가장 큰(작은) 데이터를 정렬한 후, 최하단 노드와 바꾸는 형식으로 구현한다.

※ 유의사항은 반복문 조건은 indexing 조건과 실질 요소 조건을 모두 적어주어야 index error가 발생하지 않는다는 점이다.

heap = [7, 6, 5, 8, 3, 5, 9, 1, 6]
heapLength = len(heap)

for i in range(1, heapLength):
    leaf = i

    ##먼저 max heap 구조로 바꾸는 과정
    while leaf != 0:
        root = (leaf-1)//2
        if heap[root] < heap[leaf]:
            temp = heap[root]
            heap[root] = heap[leaf]
            heap[leaf] = temp
        leaf = root

print('first heap is', heap)

##min heap으로 변환
for i in range(heapLength-1, -1, -1):
    temp = heap[i]
    heap[i] = heap[0]
    heap[0] = temp

    root = 0
    leaf = 1
    while leaf < i:
        leaf = root*2 + 1
        #자식중에 더 큰 자식 찾기
        #조건문 작성은 index 조건을 먼저 작성해야 오류발생하지 않는다
        #그 후에 요소조건(value)작성
        if leaf < i-1 and heap[leaf] < heap[leaf+1]:
            leaf = leaf + 1

        #부모노드가 자식노드보다 더 작은 경우 교환
        #조건문을 위 조건문과 따로 봐야한다(elif와 같이 이어지면 안됨)
        if leaf < i and heap[root] < heap[leaf]:
            temp = heap[root]
            heap[root] = heap[leaf]
            heap[leaf] = temp

        root = leaf
        print(heap)

print(heap)