힙 정렬에 대해(1)

힙 정렬 (Heap Sort)

Heap Sort

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

- Sort in place -> 추가 배열이 필요하지 않다.

- 이진 힙(binary heap) 자료구조를 사용하여 정렬을 수행한다.

Heap의 정의

- 조건

1) complete binary tree이여야 한다.

2) heap property를 만족해야 한다.

- property는 아래 두 조건 중 하나를 만족해야 한다.

1) Max heap property

부모는 자식보다 크거나 같다

2) Min heap property

부모는 자식보다 작거나 같다.

Full binary trees와 Complete binary trees

- full binary trees

모든 레벨에 노드들이 전부 차있는 상태의 트리이다.

- complete binary tree

마지막 레벨을 제외하고는 노드들이 전부 차있으며, 마지막 레벨에서는 가장 오른쪽부터 연속하여 몇 개의 노드가 비어있는 것을 허용하는 트리이다.

힙 예시

(a)는 첫 번째와 두 번째 트리는 완전 이진 트리이며 세번째 트리는 포화 이진 트리이기 때문에 힙이 성립된다.

(b)는 첫 번째와 세 번째 트리의 자식 노드가 루트보다 크기 때문에 힙이 성립하지 않는다. 또한 두 번째 트리에서는 2레벨과 3레벨의 2와 8사이의 상하관계가 잘못 설정되어있어 힙이 성립하지 않는다 할 수 있다.

(c)는 두 트리 모두 왼쪽 가지의 노드들이 빠져 있어 완전 이진 트리나 포화 이진 트리 두 종류 모두 성립할 수 없어 힙이 아니라고 할 수 있다.

힙은 동일한 데이터를 가지고 있더라도 여러 정렬 형식에 따라 다른 데이터 분포를 보일 수 있다.

힙의 표현

- 힙은 일차원 배열로 표현이 가능하다. => A[1 ~ n] (이 때 n은 노드의 총 개수를 의미한다.)

1) 루트 노드 : A[1]

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

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

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

일반적인 트리 구조에 따르면 일차원 배열로 트리를 표현하였을 때 각 노드들의 부모 노드에 대한 정보가 정확하게 표시되지 않는다는 문제가 있다.

힙의 경우에는 일차원 배열로 데이터를 저장하더라도 완전 이진 트리구조를 정확하게 지키기 때문에 순서가 일정하고 그에 따라 부모와 자식간의 관계를 정확하게 표시할 수 있게 된다.

기본적인 힙 연산 : Max - Heapify

- 전체를 힙으로 만들자.

전제 조건 : 트리의 전체적인 모양은 반드시 완전 이진 트리의 형태여야 한다.

루트 노드의 왼쪽, 오른쪽 자식들은 힙의 조건을 만족하나 루트 노드만 힙의 조건을 만족하지 않을 때 수행한다.

* 예시

루트 노드만이 4로 자식 노드들보다 크기가 작다는 문제가 발생한다.

루트 노드의 값과 두 자식 노드의 값을 비교하여 루트 노드의 값이 더 클때까지 자식 노드와 교환을 하는데, 두 자식 노드 중 더 큰 값을 가진 자식 노드와 교환을 수행한다.

Heapify에 대한 슈도 코드 (Recursive version)

MAX_HEAPIFY(A, i) { // 노드 i를 루트로 하여 서브트리들을 heapify한다.

if no child of A[i]

return;

k <- index of the biggest child of i;

if A[i] ≥ A[k]

return;

exchange A[i] and A[k];

MAX_HEAPIFY(A, k); //순환적으로 반복한다.

}

-> 루트 노드에 대한 heapify는 i에 1을 넣어줌으로써 가능해진다.

Heapify에 대한 슈도 코드 (Iterative version)

MAX_HEAPIFY(A, i) { // 노드 i를 루트로 하여 서브트리들을 heapify한다.

while A[i] has a child do //A[i]가 자식을 가지고 있을 때에만 반복한다.

k <- index of the biggest child of i;

if A[i] ≥ A[k]

return;

exchange A[i] and A[k];

i = k; //자식 노드단의 인덱스를 i로 바꾸어준 후 반복을 계속 수행한다.

end.