힙 / 힙 정렬 (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의 데이터는 비워 놓는다.
최대 힙으로 배열을 구성한다.
힙 정렬을 사용하여서 배열을 정렬한다.