[Data Structure] 힙 (Heap)

✔ 힙

힙(Heap)이란?

• 배열을 기반으로 한 완전 이진 트리의 일종이므로 이진 힙(Binary Heap)이라고도 불림
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 우선순위 큐 구현을 위해 만들어진 자료구조
• 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져나가게 됨

힙의 특징

1. 힙의 종류로는 최대 힙과 최소 힙이 존재
   • 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
   • 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
2. 반정렬 상태를 유지
   • 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입한 후,
     새로운 노드를 부모 노드들과 교환하여 힙을 재구성
   • 최대 힙(최소 힙)에서 최대값(최소값)은 루트 노드이므로 루트 노드를 삭제한 후,
     삭제된 루트 노드의 자리에 힙의 마지막 노드를 가져온 후 힙을 재구성
   • 삽입과 삭제에 모두 시간 복잡도 O(N)을 가지며 최대값(최소값)을 접근할 때는 루트 노드를 찾으면 되므로 O(1)
3.  힙을 저장하는 표준적인 자료구조는 배열
   • 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않음
4. 부모 노드와 자식 노드의 관계를 가짐
   • 왼쪽 자식 노드의 인덱스 = 부모 인덱스 * 2
   • 오른쪽 자식 노드의 인덱스 = 부모 인덱스 * 2 + 1
   • 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
5.  힙 트리는 중복된 값을 허용 (단, 이진 탐색 트리는 중복값을 허용하지 않음)

힙은 언제 사용할까?

• 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산에 사용