힙 이론

전체 코드

// 이진 트리
// 이진 트리 개념
// 각 노드가 최대 두개의 자식 노드를 가지는 트리
// 이진 검색 트리 특징
// 왼쪽을 타고 가면 현재 값보다 작다.
// 오른쪽을 타고 가면 현재 값보다 크다

// 이진 검색 트리 문제
// 무식하게 추가하면 , 한쪽으로 기울어져서 균형이 깨진다. 트리 재배치를 통해 균형을 유지하는 것이 과제 (AVL, RED-BLACK)
// 리스트와 똑같아짐

// 힙트리
// 힙트리 특징
// 힙트리 1법칙 :  부모노드가 가진 값은 항상 자식 노드가 가진 값보다 크다.

// 힙트리 구조
// 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다.
// 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 채워야 한다.

// 힙트리 2법칙 : 노드 개수를 알면 트리 구조는 무조건 확정할 수 있다.

// 힙트리 구현
// 따라서 배열을 이용해서 힙구조를 바로 표현할 수 있다.
int[]heap = new int[5]
// i번 노드의 왼쪽 자식은 [(2*i)]+1] 번
// i번 노드의 오른쪽 자식은 [(2*i)]+2] 번
// i번 노드의 부모는 [(i-1)/2] // 소수점은 버림

// 새로운 값 추가
// 31추가
// 힙트리 2법칙 : 노드 개수를 알면 트리구조는 무조건 확정할 수 있다.
// 도장깨기 시작

// 최대값 꺼내기
// 힙트리 특성상 최대값은 무조건 루트 노드에 있는 값이다.
// 따라서 32를 꺼내보자
// 1단계 최대값을 먼저 제거한다.
// 힙트리 2법칙 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.
// 2단계 제일 마지막에 위치한 데이터를 루트로 옮긴다.
// 부모 노드가 가진 값은 항상 자식노드가 가진 값보다 커야 된다.
// 역도장 깨기를 시작

• 이진 검색 트리 특징
  

• 이진 검색 트리 문제점
  

• 힙트리 구조

• 데이터 개수가 5개인 경우의 힙 트리 구조

• 힙트리 구현

---

1. 힙(Heap) 트리 개념 정리

1.1 힙의 종류

1. 최대 힙(Max Heap)
   • 부모 노드의 값이 항상 자식 노드보다 크거나 같다.
   • 루트 노드에 최대값이 위치함.
2. 최소 힙(Min Heap)
   • 부모 노드의 값이 항상 자식 노드보다 작거나 같다.
   • 루트 노드에 최소값이 위치함.

1.2 힙(Heap)의 특성

• 완전 이진 트리 구조를 가짐
  • 모든 레벨이 가득 차 있으며, 마지막 레벨만 예외적으로 채워질 수 있음.
  • 마지막 레벨에서는 왼쪽부터 차례로 노드가 채워져야 함.
• 힙의 트리 구조는 노드 개수만으로도 결정됨.
• 배열로 효율적으로 구현할 수 있음.
  • 노드의 위치를 배열의 인덱스로 표현 가능.

1.3 힙의 배열 표현

힙을 배열로 구현하면 다음과 같은 규칙이 성립합니다.

• 왼쪽 자식 노드: 2 * i + 1
• 오른쪽 자식 노드: 2 * i + 2
• 부모 노드: (i - 1) / 2

예제 트리 (최대 힙)

       50
      /  \
    30    20
   /  \   /
  10  15  5

위의 트리는 배열로 표현하면:

int[] heap = {50, 30, 20, 10, 15, 5};

---

2. 힙 연산

2.1 삽입 연산 (Heap Push)

1. 힙의 규칙을 유지하기 위해 새로운 값을 마지막 자리에 추가.
2. 부모와 비교 후 더 크다면 자리 교환 (도장 깨기) 반복.

---

2.2 삭제 연산 (Heap Pop)

1. 루트 노드 (최댓값)를 제거
2. 마지막 노드를 루트로 이동
3. 자식 노드들과 비교하여 자리를 찾아감 (역 도장 깨기)

출력 결과

50
40, 30, 20, 10, 15, 5

(50 제거 후, 40이 루트로 올라가고 자리 교환)

---