Heap Sort

Definition :

'부모의 값이 자식의 값보다 항상 크거나 작은' 힙의 특성을 이용하여 정렬하는 알고리즘

---

Properties :

1) Heap order property

- 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다 (MAX Heap)

- 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다 (MIN Heap)

 

2) Heap shape property

- 트리의 모양은 완전이진트리

- 리프 노드는 모두 왼쪽에 쏠려 있다

 

3) 부분 순서 트리

- 부모 : 자식 간의 관계는 일정하지만, 형제 노드 사이의 대소 관계는 일정하지 않다

---

완전이진트리

: 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리

  한 노드는 최대 두 개의 자식 노드를 가진다.

 

 

 

1차원 배열로 표현이 가능하며, 부모 : 자식 노드 관계를 공식화 할 수 있다.

 

 

# index 0부터 시작

parent = (index - 1) // 2
left_index = 2 * index + 1
right_index = 2 * index + 2

 

 

완전이진트리와 힙의 차이 :

- 완전이진트리는 [왼쪽 자식 노드의 값 < 부모 노드 < 오른쪽 자식 노드의 값]

- 힙은 [부모 노드의 값 < 자식 노드의 값 or 부모 노드의 값 > 자식 노드의 값]

 

==> 힙은 우선순위 정렬에, 완전이진트리는 탐색에 유리하다.

---

Heapify

 

- Heap properties를 만족하도록 하기 위해 자료구조를 정렬하는 연산

 

1) 입력받은 인덱스 노드의 자식 노드를 설정하고, {부모 노드의 값이 자식 노드의 최대값보다 작다면} 위치를 바꾼다

2) 바꾼 위치에 대한 subtree 또한 Heap properties를 만족하는지 자기 자신을 호출하여 확인 및 정렬

 

# O(logn)
def heapify(unsorted, index, heap_size) :
    max_idx = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2

    if left_index < heap_size and unsorted[left_index] > unsorted[max_idx] and unsorted[left_index] => unsorted[right_index]:
        max_idx = left_index
		
    if right_index < heap_size and unsorted[right_index] > unsorted[max_idx] and unsorted[right_index] >= unsorted[left_index] :
        max_idx = right_index
				
    if max_idx != index :
        unsorted[max_idx], unsorted[index] = unsorted[index], unsorted[max_idx]
        heapify(unsorted, max_idx, heap_size)

 

---

Heap_sort

 

- 주어진 자료구조를 힙 구조로 만든다

- 최대값이 루트 노드로 오는 최대 힙 구조의 특성을 이용하여, 루트 노드를 최소 값을 갖는 노드와 바꿔가며 최소 힙 구조를 만든다

 

def heap_sort(unsorted) :
       n = len(unsorted)
		
       # 주어진 배열을 힙 구조로 만들기
       # O(N)
       for index in range (n // 2 - 1, -1, -1) :
           heapify(unsorted, index, n)
		
        # 힙의 최대값을 맨 뒤로 보내며 계속 힙 속성을 유지하며 배열 정렬
        # 맨 뒤로 보낸 최대값은 포함시키지 않으면서, 오름차순으로 정렬
        # O(logN) N번 반복 -> O(NlogN)
        for i in range (n - 1, 0, -1) :
            unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
            heapify (unsorted, 0, i)
		
        return unsorted

 

# 자료구조를 힙 구조로 만드는 과정
# 초기 배열은 [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]

unsorted = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]

index = 4 / left_index = 9 / right_index = NULL
unsorted[4] (= 7) unsorted[9] (=1) ==> 힙 성질 만족

index = 3 / left_index = 7 / right_index = 8
unsorted[3] (= 14) unsorted[7] (=2) unsorted[8] (=8) ==> 힙 성질 만족

index = 2 / left_index = 5 / right_index = 6
unsorted[2] (= 10) unsorted[5] (= 9) unsorted[6] (= 3) ==> 힙 성질 만족

index = 1 / left_index = 3 / right_index = 4
unsorted[1] (= 4) unsorted[3] (= 14) unsorted[4] (=7) ==> 힙 성질 불만족

// unsorted[left_index] > unsorted[parent] 이므로, 왼쪽과 자리 교체
unsorted = [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]
// parent != index 조건문에 해당
// 자리 교체가 일어난 후, 부모가 바뀐 서브트리에 대한 성질 만족 여부 확인 및 정렬 

index = 3 / left_index = 7 / right_index = 8
unsorted[3] (= 4) unsorted[7] (= 2) unsorted[8] (= 8) ==> 힙 성질 불만족

// unsorted[right_index] > unsorted[parent] 이므로, 오른쪽과 자리 교체
unsorted = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
// parent != index 조건문에 해당
// 자리 교체가 일어난 후, 부모가 바뀐 서브트리에 대한 성질 만족 여부 확인 및 정렬

index = 8 / left_index = NULL / right_index = NULL ==> 자식이 없으므로 PASS

--> 최종 array = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

 

# 최대 힙 구조를 최소 힙 구조로 만드는 과정
# 최대값을 갖는 노드와 최소값을 갖는 노드를 바꾸고, 사이즈를 1씩 줄여준다
# i = 9일 때의 과정

unsorted = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
-> unsorted = [1, 14, 10, 8, 7, 9, 3, 2, 4, 16] / i = 9 
=> 16을 제외한 1 ~ 4까지에 대해서 힙 정렬

index = 0 / left_index = 1 / right_index = 2
unsorted[0] (=1) unsorted[1] (=14) unsorted[2] (=10) => 힙 성질 불만족

// unsorted[left_index] > unsorted[parent]이므로, 왼쪽과 자리 교체
unsorted = [14, 1, 10, 8, 7, 9, 3, 2, 4, 16]
// parent != index 조건문에 해당
// 자리 교체가 일어난 후, 부모가 바뀐 서브트리에 대한 성질 만족 여부 확인 및 정렬

index = 1 / left_index = 3 / right_index = 4
unsorted[1] (=1) unsorted[3] (=8) unsorted[4] (=7) => 힙 성질 불만족

// unsorted[left_index] > unsorted[parent]이므로, 왼쪽과 자리 교체
unsorted = [14, 8, 10, 1, 7, 9, 3, 2, 4, 16]
// parent != index 조건문에 해당
// 자리 교체가 일어난 후, 부모가 바뀐 서브트리에 대한 성질 만족 여부 확인 및 정렬

index = 3 / left_index = 7 / right_index = 8
unsorted[3] (=1) unsorted[7] (=2) unsorted[8] (=4) => 힙 성질 불만족

// unsorted[right_index] > unsorted[parent]이므로, 왼쪽과 자리 교체
unsorted = [14, 8, 10, 4, 7, 9, 3, 2, 1, 16]
// parent != index 조건문에 해당
// 자리 교체가 일어난 후, 부모가 바뀐 서브트리에 대한 성질 만족 여부 확인 및 정렬

index = 8 / left_index = NULL / right_index = NULL
--> 리프 노드에 해당하니, 탐색 종료 및 다음 케이스 진행 

--> for문 모두 진행 할 시 오름차순으로 정렬

 

---

 

최대 힙 구조로 만드는 데 O(N)

최소 힙 구조로 만드는 데 O(logN), 이를 N번 반복하기 때문에 O(NlogN)

힙 특성 유지를 위한 정렬 연산 (Heapify)은 O(logN)

 

최소 힙 구조만 만든다면 O(logN)

최대 힙 구조만 만든다면 O(logN)

최소 -> 최대 or 최대 -> 최소 힙 구조를 만든다면 O(NlogN)