1. 힙(Heap)이란?

힙(Heap)은 특별한 종류의 트리 기반 자료구조로, 주로 우선순위 큐(priority queue)와 같은 응용에서 사용되며, 데이터를 효율적으로 관리하는 데 사용됩니다. 힙은 부모 노드와 자식 노드 간의 관계에 따라 정의되며, 일반적으로 부모 노드가 자식 노드보다 작은 값을 갖는 최소 힙과, 부모 노드가 자식 노드보다 큰 값을 갖는 최대 힙으로 나뉩니다.

2. 힙의 구성 요소

• 노드 (Nodes): 힙의 각 항목을 나타내며, 각 노드는 하나 이상의 자식 노드를 가질 수 있습니다.

• 부모와 자식 관계 (Parent-Child Relationship): 부모 노드와 자식 노드 간의 관계는 힙의 핵심입니다. 최소 힙에서는 부모가 항상 자식보다 작은 값을 가지며, 최대 힙에서는 그 반대입니다.

  • 임의로 첫번째(root) 노드의 인덱스를 1로 잡고 생각한다. ( 0 은 사용하지 않는다)
  • 부모 인덱스 = (자식 인덱스) / 2
  • 왼쪽 자식 인덱스 = (부모 인덱스) *2
  • 오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1

3. 힙의 기본 동작

1. 삽입 (Insertion):
   • 삽입 작업은 힙에 새로운 요소를 추가하는 과정입니다.
   • 새로운 요소는 일반적으로 힙의 맨 아래 레벨에 위치하게 됩니다.
   • 삽입 후, 새로운 요소를 힙의 특성에 따라 재배열하여 힙 속성을 유지합니다.
   • 최소 힙의 경우, 새로운 요소는 부모 노드보다 크거나 같은 값을 가져야 합니다. 최대 힙의 경우, 새로운 요소는 부모 노드보다 작거나 같은 값을 가져야 합니다.
2. 삭제 (Deletion):
   • 삭제 작업은 힙에서 루트 노드를 제거하고 반환하는 과정입니다.
   • 루트 노드를 제거한 후, 나머지 노드들을 힙의 특성에 따라 재배열하여 힙 속성을 유지합니다.
   • 최소 힙의 경우, 루트 노드는 힙 내에서 가장 작은 값이므로, 이 값을 반환하면서 삭제합니다. 최대 힙의 경우, 가장 큰 값을 반환하면서 삭제합니다.

4. 힙의 여러 가지 종류

• 최소 힙 (Min Heap): 부모 노드가 자식 노드보다 작은 값을 가지는 힙입니다. 가장 작은 값이 루트 노드에 위치합니다.
• 최대 힙 (Max Heap): 부모 노드가 자식 노드보다 큰 값을 가지는 힙입니다. 가장 큰 값이 루트 노드에 위치합니다.
  

5. 힙 활용문제 풀어보기

Q1: 최소 힙(Min Heap)과 최대 힙(Max Heap)의 주요 차이점은 무엇인가요?
Q2: 힙의 시간 복잡도는 어떻게 되나요?