힙 / 힙 정렬 (Heap / Heap Sort)

힙 / 힙 정렬

 

[Heap / Heap Sort]

 

 

힙 (Heap) [n 더미]

: 완전 이진 트리의 일종으로, 우선 순위 큐를 위하여 만들어진 자료 구조

 

여러 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아 내도록 만들어진 자료 구조이다.

 

 

<힙 트리의 예>

※ 힙 트리에서는 중복된 값을 허용

 

이러한 특징으로 힙 트리에서는 두 종류가 존재한다.

1. 최대 힙 (Max Heap)

: key(부모노드) >= key(자식노드)

(부모노드의 키 값이 자식노드의 키 값 보다 크거나 같음)

2. 최소 힙 (Min Heap)

: key(부모노드) <= key(자식노드)

(부모노드의 키 값이 자식노드의 키 값 보다 작거나 같음)

 

힙 트리를 이용한 배열 구현 

※ 편의상 배열의 index 0의 데이터는 비워 놓는다.

각 노드의 배열 위치 구성 조건은 다음과 같다.

 

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2

오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1

ex) 6 (c의 인덱스) = 3 (a의 인덱스) * 2

7 (h의 인덱스) = 3 (a의 인덱스) * 2 + 1

 

 

위 배열을 최대 힙으로 구성하는 과정

 

※ 자식 노드가 존재하는 가장 큰 인덱스를 가진 노드부터 시작

※ a<b<.....<g<h

①“b” (index=4)의 자식노드 “g” (index=8)과 비교 => b < g 이므로 자리 교체

 

 

②“a” (index=3)의 왼쪽 자식노드 “c” (index=6)과 비교

“a” (index=3)의 오른쪽 자식노드 “h” (index=7)과 비교

=> a < c , a < h 이므로 a 와 h를 교체

 

③“e” (index=2)의 왼쪽 자식노드 “g” (index=4)과 비교

“e” (index=2)의 오른쪽 자식노드 “f” (index=5)과 비교

=> e < g , e < f 이므로 e 와 g를 교체

 

④“d” (index=1)의 왼쪽 자식노드 “g” (index=2)과 비교

“d” (index=3)의 오른쪽 자식노드 “h” (index=3)과 비교

=> d < g , d < h 이므로 h 와 d를 교체

 

<최대 힙으로 구성한 배열>

위와 같이 배열이 최대 힙으로 구성 되었다.

 

<힙 정렬을 이용한 배열 정렬>

정렬 과정은 다음과 같다. (★는 최대 힙으로 구성됨)

1. n개의 노드에 대한 완전이진트리를 구성한다.

2. 해당 트리를 최대 힙으로 구성한다.

3. 루트노드(index=1)를 가장 말단의 노드(index=8)과 교환

4. 정렬된 데이터를 제외하고 나머지 데이터로 트리를 구성

정렬이 완료될 때 까지 2~4의 과정을 반복한다.

 

 

정리

정렬하고 싶은 힙 트리를 배열로 구성

※ 편의를 위해서 index 0의 데이터는 비워 놓는다.

 

최대 힙으로 배열을 구성한다.

 

힙 정렬을 사용하여서 배열을 정렬한다.