(Python)힙 정렬

 

힙 정렬은 힙 트리 구조를 이용하는 정렬 방법이다.

 

이진트리 / 힙 

 

이진트리란 컴퓨터 안에서 데이터를 표현할때 데이터를 노드에 담아 노드를 두개씩 이어 붙이는 구조

이진트리는 모든 노드의 자식 노드가 2개이하인 노드이다.

맨 위는 루트 맨 아래는 리프

 

완전 이진 트리:  데이터가 루트노드로 시작해 자식노드가 왼쪽,오른쪽 으로 차근차근 들어가는 구조의 이진 트리이다.

중간에 빈 값 없이 꽉 차 있다.

 

힙 : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리, 최대힙은 부모 노드가, 자식 노드 보다 큰 힙이다.

- 힙은 중복값을 허용한다. 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 이기 때문

 

 

만약 자식노드가 부모노드보다 큰 경우 힙 정렬을 하는데 이것을 힙 생성 알고리즘이라고 한다.

정렬을 한 후에도 여전히 자식이 존재하는 경우 또 자식 중에서 더 큰 자식노드와 자신의 위치를 바꿔야한다.

 

삽입 또는 삭제가 일어나게 되면 경우에 따라 최대힙의 조건이 깨질 수 있다. >> 이럴때 조건을 만족하게 

노드들의 위치를 바꿔가며 힙을 재구조화(Heapify) 해준다.

 

힙 생성 알고리즘의(heapify) 시간 복잡도: 한번 수행될때 수행시간은 트리의 높이와 같기때문에 O(logN) 이다.

힙을 구성하는 시간 복잡도: 비어있는 힙에 주어진 n개의 요소를 차례대로 삽입연산을 해야 하므로, O(nlogN)이다.

 

코드:

array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
# 상향식

def heap_sort(array):
    n = len(array)
    # 전체 트리 구조를 최대 힙 구조로 바꿈
    for i in range(n):
        c = i
        while c != 0:               # c는 자식노드
            r = ( c-1 ) // 2        # r은 부모노드 의 인덱스
            if (array[r] < array[c]):   # 자식이 더크면 부모와 교환
                array[r], array[c] = array[c], array[r]
            c = r               # 자식노드에서 부모노드로 이동
            # print(array)

    # 크기를 줄여가면서 heap 구성
    for j in range(n-1, -1, -1):
        array[0] , array[j] = array[j], array[0]  # 첫 값과 맨 뒤에 있는 원소를 바꿈
        r = 0   # 루트의 위치
        c = 1   # 변수 이용
        while c < j:
            c = 2 * r +1    # 자식
            # 자식 중 더 큰 값 찾기
            if (c < j - 1) and (array[c] < array[ c+1 ]):
                c += 1
            # c 와 c+1 중 비교해서 더 큰값을 c 에 넣어주는 것
            # 범위를 벗어나지 않게 c<j-1 로 막아준것

            # 루트보다 자식이 크다면 교환
            if (c < j) and (array[r] < array[c]):
                array[r], array[c] = array[c], array[r]
            r = c
            # 다시 c 를 r로 이동시켜 재귀적으로 동
    print(array)
heap_sort(array)