개발 공부 - [정렬] 힙 정렬(heap sort) -1 (Section 3)

 Heap과 Heapsort

- 최악의 경우 시간복잡도 O(nlog2n)

- Sorts in place - 추가 배열 불필요 (mergesort와 다르다!)

- 이진 힙(binary heap) 자료구조를 사용

Heap은 

1) complete binary tree 

2) heap property 를 만족 

max heap property : 부모는 자식보다 크거나 같다 = 위에 노드의 값이 더 커야 한다.

min heap property : 부모는 자식보다 작거나 같다

트리는 계층적 관계를 표기하기 위해서 사용

이진트리는 한 부모가 두개의 자식을 가지고 있는 것

full binary tree : 모든 레벨에 노드들이 꽉 차 있어야 함

(단일 노드만 있어도 풀 바이너리 트리이다!)

complete binary tree : 마지막 레벨을 제외하면 완전히 차 있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개 노드가 비어있을 수 있음.

(이거는 왼쪽은 거진 메꿔져 있어야 정상.)

동일한 데이터를 가지더라도 서로 다른 모양의 힙일 수 있다.

(힙 조건만 만족하면 데이터 위치는 중요하지 않음)

힙은 일차원 배열로 표현가능하다. A[1...n]

루트 노드 A[1].

A[i]의 부모 = A[i/2]

A[i]의 왼쪽 자식 = A[2i]

A[i]의 오른쪽 자식 = A[2i + 1]

1의 왼쪽 자식은 2

1의 오른쪽 자식은 3

2의 부모는 1

3의 부모는 1

이런 식으로 계산 가능하다.

Heap을 이용해서 정렬을 하기 위한 기본 연산 :  Max Heapify

: 전체를 힙으로 만들어라.

- 트리의 전체 모양이 complete binary tree여야 한다.

유일하게 루트만이 heap property를 만족하지 않음. (부모가 없으니까)

- 왼쪽 subtree는 그 자체로 heap이고, 

- 오른쪽 subtree도 그 자체로 heap일 때!!

만약에 루트만 힙 조건을 만족하지 않을 경우,

조건을 만족시키기 위해 자식들 중 더 큰 쪽이 루트보다 크면 교환한다.

그런 식으로 밑까지 내려 보냄.

요렇게 heap 조건을 만족시키는 이진 트리로 만듬.

교수님 따르릉 하고 끝남 -.-)...