힙 정렬

☝ 힙 정렬은 정렬하고자 하는 데이터를 최소힙/최대힙 형태로 바꿔 순서대로 정렬하는 알고리즘이다.

🎫 heap의 개념

힙은 완전 이진트리 형태를 기반으로 한다.특히 우선 순위를 이용할 때 유용하게 쓰인다. 또한 배열로 주어진 데이터의 인덱스를 활용 할 수 있다.
힙 구조엔 최소 힙과 최대 힙 2가지가 있는데, 최소 힙은 부모 노드가 자식 노드보다 작거나 같고, 최대 힙은 부모노드가 자식 노드보다 크거나 같다. 힙의 종류에 따라 부모노드와 자식노드의 크기를 비교하여 힙 성질을 만족할 수 있도록 위치를 바꿔준다. 이를 heapify라고 한다.

자료 구조다 보니 삽입과 삭제 연산이 가능해야 한다.
삽입 : 마지막 레벨의 비어있는 공간 중 가장 왼쪽 자리에 삽입하여 형제 노드가 아닌 부모 노드와 크기를 비교하는 아래에서 위로 향하는 heapify 연산을 통해 새로 정렬 해준다.

삭제 : 루트 노드를 삭제하고, 가장 마지막 레벨의 가장 마지막 값을 비어 있는 루트 노드에 삽입하여 위에서 아래로 향하는 heapify 연산을 해준다.

❓ 예시

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
참고

💻 힙 삽입 삭제 코드 구현 (python)

https://airsbigdata.tistory.com/146
참고

⏰ 시간 복잡도

heapify 시간 복잡도 : 최악의 경우 모든 노드 값을 비교해야 하므로 트리의 높이(log2N)에 의존적이다. 값을 비교하거나 바꾸는 연산은 O(1)이므로 O(logN)
삽입, 삭제의 시간 복잡도 : 삽입/삭제하는데 드는 연산 O(1), heapify하는 데에 드는 시간은 O(logN)이 므로 O(logN)이다.
힙을 구성하는 시간 복잡도 :
비어있는 힙에 주어진 n개의 요소를 차례대로 삽입연산을 해야 하므로, O(nlogN)이다.

🎫 heap 정렬의 개념

주어진 원소들로 최대/최소 힙을 만든 후, 최대(최소) 힙의 경우 루트 노드(r)의 값과 마지막 노드(l)의 값을 교환한다. 교환을 통해 r은 자신의 자리를 찾게 되는 것이고, l의 새 위치를 찾기 위해 정렬하게 되면 루트 노드에 위치한 새로운 값 new r이 이전 루트 노드 값 r을 제외하고 이 힙 구조에서 가장 큰(작은) 값이 된다. 이를 반복하면 정렬이 되는 것이다.

❓ 예시

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
참고

💻 힙 정렬 코드 구현 (python)

def heap_sort(unsorted):
    n = len(unsorted)
    #최대 힙 만들기
    #최소힙은 부등호만 반대로 바꿔주면 됨
    for i in range(1, n):
        child = i
        while child != 0:
            parent = (child-1)//2
            if unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]
            child = parent #최대값이 루트까지 도달 할 수 있도록

    #힙 만들기
    for node in range(n-1, -1, -1):
        #루트 노드와 마지막 노드를 교환
        #값이 큰 순서대로 힙의 끝에 저장됨
        unsorted[0], unsorted[node] = unsorted[node], unsorted[0]
        parent = 0
        child = 1

        # 정렬이 미완료 된 노드들 사이에서
        # 마지막 노드 자리리 보내준 루트 노드를 제외한 가장 큰 값을 찾고
        # 루트 노드 자리로 온 마지막 노드의 자리 찾기
        while child < node:
            child = parent*2 + 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 찾기 위해
            if child < node-1 and unsorted[child] < unsorted[child+1]:
                child += 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 루트 자리로 보내기 위한 과정
            if child < node and unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]

            parent = child

    return unsorted



if __name__ == '__main__' :
    arr = list(map(int, input().split()))
    print(heap_sort(arr))

⏰ 시간 복잡도

우선 힙을 만드는 복잡도는 O(n)이다. 그 다음 n개의 요소를 크기 순서대로 루트 노드에 올려주는 heapify를 해줘야 하므로 O(nlogN).
따라서 O(n) + O(nlogN) = O(nlogN)이다.