히프의 개념과 응용

📌 히프의 개념과 응용

💡 히프(Heap)의 정의

1. 최대 트리와 최대 히프
   1. 최대 트리(Max Tree)
      1. 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값보다 크거나 같은 트리
   2. 최대 히프(Max Heap)
      1. 최대트리 이면서, 완전 이진트리.

2. 최소 트리와 최소 히프
   1. 최소 트리(Min Tree)
      1. 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값다 작거나 같은 트리
   2. 최소 히프(Min Heap)
      1. 최소트리 이면서, 완전 이진트리.

최대 히프의 root 노드는 항상 모든 노드들보다 큰 값을 가지고 있다.
최소 히프의 root 노드는 항상 모든 노드들보다 작은 값을 가지고 있다.

이는 가장 큰 값과 가장 작은 값을 찾기 쉬운 자료구조이다.

💡 우선 순위 큐(Priority Queue)

1. 우선 순위 큐의 특징
   1. 일반적인 큐의 특징인 선입 선출 방식이 아닌, 우선 순위의 순서대로 처리되는 큐이다.
      • 비행기 탑승 대기, OS의 작업스케쥴링 등
   2. 우선 순위 큐의 구현 방법 비교

💡 최대 히프에 노드를 추가

1. 시간복잡도 : O(Log N)
2. 최대 히프를 배열로 구현하는 이유
   1. 배열의 끝에 노드를 추가한다.
   2. 추가된 위치의 부모노드부터 루트노드까지 기존 노드들의 데이터와 비교하면서 최대 히프를 재구성한다.
      • [i]에 저장된 노드의 부모노드의 위치 : i // 2
   • Depth 가 중요하게 된다.
   • Depth 가 K 인 트리에서 노드 수는 2 ** K - 1개 이다.

💡 최대 히프에서 노드를 삭제

1. 개념
   1. 히프에서의 노드 삭제는 항상 루트 노드에서만 발생한다.
   2. 루트 노드를 삭제한 후, 히프를 재구성한다.

2. 최소 히프를 재구성하는 방법
   1. 루트 노드를 삭제한 후, 마지막 노드를 루트로 변경한다.
      • 일단 루트로 올리고, 값을 비교하면서 그 값을 교체하는 방식.
      • 마지막 노드의 값이 아닌 다른 값이 들어가면 이진트리가 아니게 되는 수가 있다.
   2. 루트 노드부터 아래로 순회하면서 노드의 값을 비교하며 히프를 재구성한다.