힙 [heap]

우선 순위 큐(Prority Queue)를 구현하기 위한 완전 이진 트리(느슨한 정렬상태 - 반 정렬 상태)

힙은 중복값을 허용 → 최대, 최소를 구하기 쉬운 자료구조

• 최대 힙: 부모 노드 ≥ 자식 노드 (root node가 최댓값)
• 최소 힙: 자식 노드 ≥ 부모 노드 (root node가 최솟값)

시간 복잡도

• 삽입: O(logN)
• 삭제: O(logN)
• 조회: O(1)

자바 구현 시에는 PriorityQueue 사용 → default 최소 힙으로 동작

<이미지 첨부 예정>

<heap 구조로 이루어진 배열 a>

• 부모 노드: index=0
• 왼쪽 자식 노드: a[I*2+1] ⇒ 동일 선상의 형제 노드를 제외하기에 1을 더해줌
• 오른쪽 자식 노드: a[I*2+2] ⇒ 형제 노드의 자식 2명을 지나야 하기에 2더해줌

삽입 / 삭제

• 삽입 및 삭제 발생 시 최대 힙의 조건이 깨질 수 있음(부모가 자식보다 작아지는 경우) ⇒ 재구조화(heapify)를 통해 해결
• 삽입 삭제의 연산 자체는 O(1)이지만 heapify과정이 있어서 O(logn)의 시간 복잡도를 가짐