💡 [자료구조] Heap이란?

💡 힙(Heap)이란?

정식명은 Heap tree, 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리에요

• 삽입/삭제의 속도 때문에 완전 이진 트리로 나타내며, 대개 배열로 표현하는데 계산을 편하게 하기 위해 인덱스는 1부터 사용해요
• 두 종류, 최대 힙(부모 노드가 항상 자식들보다 큰 힙)과 최소 힙(부모가 항상 자식들보다 작은 힙)으로 나뉘어요
• 최댓값(최솟값)을 O(1)안에 찾을 수 있어요
• 데이터의 삽입/삭제는 O(logN)이 소요돼요
• 데이터의 삽입은 다음 프로세스로 이루어져요

1. 가장 끝의 자리에 노드 삽입
2. 그 노드와 부모 노드를 비교하여 규칙(최대/최소)에 맞으면 보존, 아니면 교환
3. 규칙에 맞을 때까지 2번 과정 반복

• 데이터의 삭제는 루트 노드만 가능하며, 다음 프로세스로 이루어져요

1. 루트 노드(최상위 노드)를 제거
2. 그 자리에 가장 마지막 노드 삽입
3. 올라간 노트와 자식 노드들을 비교
4. 1. (최대 힙) 부모보다 더 큰 자식들 중 큰 값과 교환, 없으면 종료
   2. (최소 힙) 부모보다 더 작은 자식들 중 작은 값과 교환, 없으면 종료
5. 4번을 반복