힙(Heap)의 구조 [삽입/삭제]

[ 목차 ]

---

📢 Heap

🔊 완전 이진 트리 형태

1. 중복 값 허용
2. 반 정렬 상태

🔊 최소 값 또는 최대 값을 빠르게 찾아내는 데 유용한 자료구조

1. 최소 힙
2. 최대 힙

🔊 Heap은 배열 및 ArrayList<>로 대체로 구현한다.

📢 최소 힙과 최대 힙

🔊 최소 Heap (Min Heap)

• 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태이다.

🔊 최대 Heap (Max Heap)

• 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태이다.

📢 힙의 삽입과 삭제

🔊 최소 Heap 삽입

• 트리의 가장 끝 위치에 데이터 삽입
• 부모 노드와 키를 비교한 후 작을 경우 부모 자리를 교체를 반복해서 교체한다. 

🔊 최소 Heap 삭제

• 최상위 노드 반환 및 삭제
• 가장 마지막 위치의 노드를 최상위 노드로 위치 시킨다.
• 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리를 반복해서 교체한다.

🔊 최대 Heap 삽입

• 트리의 가장 끝 위치에 데이터 삽입
• 부모 노드와 키를 비교한 후 큰 경우 부모 자리를 교체를 반복해서 교체한다. 

🔊 최대 Heap 삭제

• 최상위 노드 반환 및 삭제
• 가장 마지막 위치의 노드를 최상위 노드로 위치 시킨다.
• 자식 노드 중 큰 값과 비교 후 부모 노드가 더 작으면 자리를 반복해서 교체한다.

📢 노트 정리

📢 Heap의 부모 / 자식 노드 찾기

출처 : 위키백과

🔊 [성질]

< 인덱스가 0부터 시작하는 경우 >

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1

2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2

3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2

< 인덱스가 1부터 시작하는 경우 >

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2

2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1

3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2

 

🔊 [예시]

Q1. index 3의 왼쪽 자식 노드?

- 부모 인덱스 : index 3

- 왼쪽 자식 : 3 X 2 + 1 = index 7

 

Q2. index 5의 부모 노드?

- 부모 인덱스 : (5 - 1) / 2 = index 2