[자료구조] 비선형 자료구조 - 힙 (Heap)

Heap 기본

• 완전 이진 트리의 일종으로, 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조
  • 우선순위 큐(Priority Queue)?
    • 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 먼저 나가는 는 자료구조
    • 참고로 Java 와 Python 은 최소 힙(Min Heap) 을 사용하여 우선순위 큐가 구현되어있음
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 일종의 반정렬 상태(느슨한 정렬 상태)를 유지함
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있음
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진트리
• 중복 값을 허용함(이진 탐색 트리는 중복 값을 허용하지 않음)

---

Heap 의 종류

• 최대 힙(Max Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(Min Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

---

Heap 삽입

• 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입
• 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴
• 최대 힙 삽입 예시

---

Heap 삭제

• 최대 힙에서 최댓값은 루트 노드이므로, 루트 노드가 삭제됨
  • 최대 힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것
• 삭제된 루트 노드에 힙의 마지막 노드를 가져온 뒤 힙을 재구성함
• 최대 힙 삭제 예시

---