개요
아래의 내용은 algorithm 레파지토리 A1sort 디렉터리에 저장되어있는 내용을 정리함
힙 정렬을 “트리 탐색 + 재귀 호출” 관점으로 이해하기 위해, 배열을 완전이진트리로 해석하는 규칙부터 시작해 heapify로 최초 힙을 구성하고, 루트-마지막 스왑과 범위 축소를 반복하며 정렬을 완성한다. 이어서 같은 힙 개념이 PriorityQueue에서 add/poll로 어떻게 활용되는지도 연결한다.
힙 자료구조와 힙의 생성 개념
힙은 완전 이진 트리의 일종으로, 각 노드의 값이 자식 노드들의 값보다 크거나 같은 (최대 힙, Max Heap) 또는 작거나 같은 (최소 힙, Min Heap) 특성을 가진 자료구조
이 때 만약 주어진 데이터가 힙구조가 아니라면 힙구조로 만들어 가는 과정이 힙의 생성(Heapify) 과정
정렬 대상과 목표
정렬 대상은 아래처럼 정렬되지 않은 배열이다.
int[] arr = {7, 6, 5, 8, 3, 5, 9, 1, 6};이 배열을 힙 정렬로 정리하는 전체 흐름은 다음 2단계로 나뉜다.
- 최초 힙 구성: 배열을 힙 구조로 바꾸기
- 정렬 진행: 루트와 마지막을 교환하면서 힙 범위를 줄이고, 깨진 힙을 다시 복구하기
트리 구조를 배열로 표현하는 규칙
힙은 완전이진트리를 배열로 표현한다. “부모 인덱스”를 기준으로 자식 인덱스를 계산해 트리를 탐색한다.
- 왼쪽 자식 인덱스:
(부모인덱스 * 2 + 1) - 오른쪽 자식 인덱스:
(부모인덱스 * 2 + 2)
이 규칙이 있으면 노드 객체/포인터 없이도 배열만으로 트리 탐색이 가능해진다.
최초 힙 구성(build-heap)
코드에서 최초 힙 구성은 아래 루프가 담당한다.
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}여기서 포인트는 “왜 arr.length / 2 - 1부터 시작하냐”다.
- 배열의 뒤쪽 절반은 대부분 리프 노드(자식이 없음)라서 heapify를 해도 내려갈 곳이 없다.
- 그래서 “부모 노드 영역”만 대상으로 잡아야 효율적이고 로직도 깔끔해진다.
arr.length를length로 넘기는 이유는, heapify가 비교/이동할 수 있는 유효 범위를 명확히 하기 위해서다.
최초 힙 구성이 끝나면 중간 상태를 확인하려고 아래 출력이 들어가 있다.
System.out.println(Arrays.toString(arr));(주석으로 “heapify 된 결과물(최초힙결과)”를 남겨둔 것도 같은 맥락이다.)
heapify: 재귀 호출의 핵심(최소힙 기준)
heapify는 “부모-자식 관계가 힙 조건을 만족하도록” 아래로 내려가며 정리하는 함수고, 네 코드는 최소힙(min-heap) 기준으로 작성되어 있다.
핵심은 다음 두 가지다.
- 부모/왼쪽/오른쪽 중 “가장 작은 값”의 인덱스를 찾는다.
- 가장 작은 값이 부모가 아니면 swap하고, swap된 자식 위치로 재귀 호출한다(더 깊은 곳까지 깨졌을 수 있기 때문).
코드 원문 흐름 그대로 보면:
static void heapify(int[] arr, int parentIdx, int length) {
int leftIdx = parentIdx * 2 + 1;
int rightIdx = parentIdx * 2 + 2;
int smallestIdx = parentIdx;
if (leftIdx < length && arr[leftIdx] < arr[smallestIdx]) {
smallestIdx = leftIdx;
}
if (rightIdx < length && arr[rightIdx] < arr[smallestIdx]) {
smallestIdx = rightIdx;
}
if (parentIdx != smallestIdx) {
int temp = arr[parentIdx];
arr[parentIdx] = arr[smallestIdx];
arr[smallestIdx] = temp;
heapify(arr, smallestIdx, length);
}
}여기서 leftIdx < length, rightIdx < length 체크를 선행하는 이유는 “자식 인덱스가 배열 범위를 넘어가는 경우”를 막기 위해서다.
그리고 재귀 종료 로직이 따로 필요 없는 이유는, 더 이상 swap이 필요 없을 때 parentIdx == smallestIdx가 되어 자연스럽게 return되기 때문이다.
루트-마지막 스왑 반복으로 정렬 완성
최초 힙 구성이 끝나면, 이제 “정렬 확정 영역”을 늘려가면서 반복한다.
위 코드의 정렬 루프는 아래다.
for (int i = arr.length - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, 0, i);
}이 루프에서 의도가 잘 드러나는 포인트는 두 가지다.
arr[0](루트)을arr[i](현재 힙의 마지막)와 교환한다.- 그 뒤에는 힙으로 취급해야 하는 길이가
i로 줄었으므로,heapify(arr, 0, i)로 “마지막 원소를 heapify 대상에서 제외”한다.
주석에 적어둔 것처럼:
- 마지막 노드는 heapify 대상에서 제외되어야 함(전체 길이는 계속 감소)
- swap 이후에는 0번째(루트)가 깨져 있을 가능성이 크므로 부모 인덱스는 항상 0부터 다시 heapify
그리고 네가 정리해둔 결론 그대로, 힙 종류에 따라 결과 방향이 달라진다.
- 최소힙 -> 내림차순 정렬
- 최대힙 -> 오름차순 정렬
정렬 이후 출력도 포함되어 있다.
System.out.println(Arrays.toString(arr));
※ 수업 내용 필기 정리 필요 (임시)
PriorityQueue로 보는 “힙을 쓰는” 정렬/운영 관점
마지막으로 너는 “pq를 통한 정렬 방법 -> 꺼낼때마다 정렬이 되는 것”을 예시로 붙여놨다.
여기서 핵심 메시지는 주석 그대로다.
- pq를 써야하는 상황: pq를 가지고 직접 정렬을 수행하기보다는, 지속적으로 값을 add하고 poll해 나가는 상황에서 사용 (매번 정렬해줄 필요가 없음)
- 최초힙 구성 복잡도:
n*log(n)(n개 add) - add 할 때 마다 복잡도:
log(n) - poll 할 때 마다 복잡도:
log(n)
예시 코드도 그대로 포함된다.
Queue<Integer> pq = new PriorityQueue<>(Arrays.asList(7, 6, 5, 8, 3, 5, 9, 1, 6));
System.out.println(pq);
System.out.println(pq.poll());
pq.add(2);여기서 포인트는 “PriorityQueue도 내부적으로 힙 성질을 유지”하기 때문에, poll()을 할 때마다 우선순위 기준(기본은 최소값 우선)으로 하나가 빠지며, add()도 힙 구조를 유지하도록 재배치가 발생한다는 점이다. 그래서 “지속적으로 들어오고 나가는 데이터”에서 매번 전체 정렬을 하지 않아도 된다.
