힙 정렬 Heap Sort 자바 Max Heap 최대 힙 Heap Sort 완전 이진 트리

🔷 1. 힙 정렬(Heap Sort)이란?

힙 정렬은 **완전 이진 트리 형태의 자료구조인 '힙(Heap)'**을 기반으로 하는 정렬 알고리즘입니다.

• 힙(Heap)은 최대 힙(Max Heap) 또는 최소 힙(Min Heap) 이 될 수 있습니다.
• 힙 정렬은 주로 최대 힙을 사용해서 내림차순 → 오름차순 정렬을 구현합니다.

---

🔷 2. 왜 힙 정렬인가? (배경과 장점)

정렬 방식	메모리 추가 필요 여부	시간 복잡도 (최악)	안정성	특징
힙 정렬	❌ in-place	O(n log n)	❌	정렬 안정성은 없지만, 메모리 효율 높음
퀵 정렬	❌ in-place	O(n²)	❌	보통 빠르지만, 최악 케이스 존재
병합 정렬	⭕ extra memory	O(n log n)	✅	메모리 사용, 안정 정렬 가능

 

힙 정렬은 추가 메모리 없이 항상 O(n log n)을 보장하며, 안정성보다 성능 보장이 중요할 때 적합합니다.

---

🔷 3. 핵심 개념: 힙 (Heap) 자료구조

✔ 최대 힙 (Max Heap)

• 부모 노드 ≥ 자식 노드
• 루트 노드는 항상 가장 큰 값

        [50]
       /    \
    [30]   [40]
    / \     /
 [10][20] [35]

---

🔷 4. 힙 정렬의 알고리즘 흐름

🧠 Step-by-step 동작 원리 (Max Heap 기반)

1. Build Max Heap
   • 배열을 최대 힙으로 만든다.
   • 시간복잡도: O(n)
2. 반복적으로 정렬
   • 최대값(루트)을 배열 마지막과 교환
   • 배열 크기를 줄이고 다시 heapify (재정렬)

💡 핵심 알고리즘

// 힙 정렬 전체 흐름
void heapSort(int[] arr) {
    int n = arr.length;

    // 1. 최대 힙 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 힙 정렬 수행
    for (int i = n - 1; i > 0; i--) {
        // 현재 루트(최대값)를 끝으로 보내기
        swap(arr, 0, i);

        // 줄어든 힙 영역에 대해 다시 최대 힙 구성
        heapify(arr, i, 0);
    }
}

// 최대 힙 조건 유지 (부모 > 자식)
void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest); // 재귀 호출
    }
}

---

🔷 5. 시각적 정리

힙 정렬 프로세스 요약

[9, 4, 7, 1, 3, 6]      ← 입력 배열
  ↓ Build Max Heap
[9, 4, 7, 1, 3, 6]      ← Max Heap
  ↓ Swap 9 ↔ 6
[6, 4, 7, 1, 3, 9]      ← 마지막 원소부터 고정
  ↓ Heapify 나머지
...
[1, 3, 4, 6, 7, 9]      ← 정렬 완료

---

🔷 6. 장단점 비교

항목	힙 정렬
시간 복잡도	항상 O(n log n)
공간 복잡도	O(1) (in-place)
안정성	❌ 안정 정렬 아님
장점	성능 일관성, 메모리 적게 사용
단점	구현 복잡도 높음, 안정 정렬 아님

 

---

🔷 7. 언제 쓰는가?

• 정렬 안정성이 필요 없는 경우
• 최악 시간 복잡도도 O(n log n) 보장이 중요한 경우
• 메모리 제약이 있는 경우
  → 예: 임베디드 시스템, 대용량 로그 분석, 커널 등

---

📌 보너스: 우선순위 큐와의 관계

힙 정렬은 우선순위 큐(PriorityQueue)의 내부 구조와 거의 동일합니다.
즉, PriorityQueue는 항상 내부적으로 힙을 유지하며 heapify 동작을 수행합니다.

---

✅ 요약

항목	설명
자료구조 기반	완전 이진 트리인 최대 힙 (Max Heap)
시간복잡도	항상 O(n log n)
공간복잡도	O(1) - 추가 공간 불필요
정렬 안정성	❌ (동일 값 간 순서 보장 안 됨)
장점	성능 예측 가능성, 메모리 효율
단점	구현 난이도, 정렬 안정성 없음

// [Heap Sort 개념 요약]
// 1. 힙(Heap)은 완전 이진 트리 구조를 가진 자료구조이며, 최대값 또는 최소값을 빠르게 찾을 수 있음.
// 2. 최대 힙(Max Heap)을 구성하면 루트에 항상 가장 큰 값이 위치하게 됨.
// 3. 모든 데이터를 힙에 Insert 한 후 DeleteMax를 반복 → 내림차순 정렬 결과 생성.
// 4. DeleteMax의 시간복잡도는 O(log n), n개 데이터에 대해 반복하므로 전체 정렬은 O(n log n).
// 5. 힙 정렬은 추가 공간 없이도 정렬 가능하지만, 본 예제는 별도의 정렬 배열을 사용함.

---

1. 필드(Fields) ― 힙의 상태를 보관

변수	의미	주의점
final int heapSize = 100	예제용 상수(사용 안 됨)	실제 용량은 MaxSize로 제어
int[] heap	힙 배열. index 1부터 사용 → heap[1]이 루트	0번은 비워 두어 수학적 식(i/2, i*2)을 간결화
int n	현재 원소 수(힙의 높이 X)	삽입·삭제 시 증감
int MaxSize	최대 허용 크기	isFull() 가드에서 사용

 

✏️ 학습 포인트

• 힙을 “완전 이진트리”로 보려면 배열+인덱스 규칙을 기억
  parent = i/2, left = i*2, right = i*2+1.

---

2. 생성자(Constructor)

public Heap(int sz) {
    MaxSize = sz;
    heap    = new int[MaxSize + 1];  // index 1 기반
    n       = 0;
}

• 동적 크기 지원: 외부에서 용량을 결정 → 재사용·테스트 쉬움.
• index 1 시작: 트리 연산을 단순화, 코드 가독성↑.

---

3. 핵심 연산 메서드

3-1. Insert(int x) ― “올라가기(Sift-Up)”

1. 가드 isFull() → 오버플로 방지.
2. 꼬리 노드 추가 n++, i = n.
3. 부모와 비교하며 상승 (while(i>1 && heap[i/2] < x)).
4. 삽입 확정 heap[i] = x.

알고리즘 복잡도 : O(log n) (힙 높이만큼 이동)

3-2. DeleteMax() ― “내려가기(Sift-Down)”

1. 가드 isEmpty() → 언더플로 방지.
2. 루트 저장 → max 반환값.
3. 마지막 원소 lastE를 루트에 놓고 크기 감소.
4. 더 큰 자식이 있는 동안 내려가기 (while (j<=n) …).
5. lastE 확정 위치 저장.

포인트

• 루트 ↔ 마지막 요소 스왑 → 완전 이진트리 유지.
• “더 큰 자식”을 택해 내려가야 Max-Heap 불변식이 유지됨.
• 복잡도 역시 O(log n).

3-3. peek() ― 최대값 조회(읽기 전용)

• 배열 1번 요소 반환.
• 현재 코드 오류: heap[0] 참조 → heap[1]로 수정 필요.

---

4. 보조 메서드 & 예외 가드

메서드	용도
isEmpty() / isFull()	가드 절. 외부에서 상태 체크 가능
HeapEmpty() / HeapFull()	콘솔 메시지 or 커스텀 예외(확장 가능)
display()	디버깅용 시각화. 인덱스를 함께 출력해 트리 구조 추적

 

---

5. 힙 정렬과의 연결 고리

Heap Sort 절차
① 정렬 대상 원소를 Insert로 모두 힙에 쌓는다 → Build Heap 단계
② DeleteMax()를 반복해 꺼내며 배열 끝에 채운다
 → 내림차순 결과가 만들어짐
③ n번 삭제 후 정렬 완료

시간 복잡도

• Build : O(n) (반복 Insert면 O(n log n)이지만, 배열 힙화는 O(n))
• DeleteMax n번 : O(n log n)
• 총 O(n log n) (공간 O(1) 가능)

---

6. 개선·확장 아이디어 (Pros / Cons 관점)

영역	보완점	장점	단점·Trade-off
예외 처리	HeapFullException, HeapEmptyException 사용자 정의	명확한 오류 흐름	코드량 증가
제네릭화	int → Comparable<T>	재사용성↑ (우선순위큐로 활용)	오토박싱 비용
동적 크기	배열 부족 시 더블링(resize)	실제 우선순위큐처럼 사용 가능	O(n) 재할당
in-place Sort	별도 sorted[] 없이 배열 자체 힙화	메모리 절약, 교과서 표준	코드 가독성 ↓

 

---

7. 한눈에 보는 로직 흐름

Insert(x)
  ↑
[끝에 자리 확보] ← n++
  ↑
[부모와 비교] (i/2)
  ↑
[크면 swap] … 반복

DeleteMax()
   |
[루트 → max 반환]
   |
[마지막 원소 → 루트]
   |
[더 큰 자식과 swap] (i*2 or i*2+1)
   |
[힙 속성 회복] … 반복

이 “올라가기 / 내려가기” 두 연산이 힙 정렬의 엔진입니다.

---

✅ 정리 키워드

• 완전 이진트리 / 배열 인덱스 1 시작
• MaxHeap 불변식 : 부모 ≥ 자식
• Sift-Up / Sift-Down : O(log n)
• Heap Sort = Build Heap + DeleteMax×n → O(n log n)
• 공간 : 배열 재사용 시 O(1) 가능