[자료구조] Heap

※ 2022년 1월 10일에 작성된 글입니다.

🌳 Heap

부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리

Heap의 종류

• max heap
  부모 노드의 키 ≥ 자식 노드의 키
• min heap
  부모 노드의 키 ≤ 자식 노드의 키

Heap의 높이

• n개의 노드를 가지고 있는 힙의 높이는 O(log n)

마지막 레벨 h 외에는 각 레벨 i에 2^i-1개의 노드 존재

Heap의 구현 방법

• 배열

완전 이진 트리이므로 각 노드에 번호(배열의 인덱스)를 붙일 수 있다.

0	1	2	3	4	5	6	7	8	9	10
	9	7	6	5	4	3	2	2	1	3

부모 노드와 자식 노드를 찾기가 쉽다.

• 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
• 부모의 인덱스 = 자식의 인덱스 / 2

Heap의 연산

• upheap
  삽입
• downheap
  삭제

upheap

1. 힙에 새로운 요소가 들어 오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 힙의 성질을 만족할 때까지 부모 노드와 교환한다.

downheap

1. 루트 노드를 삭제한다.
2. 마지막 노드를 루트 노드로 이동한다.
3. 이동한 노드를 힙의 성질을 만족할 때까지 자식 노드와 교환한다.

최대 힙에서의 삭제
= 가장 큰 키 값을 가진 노드 삭제
= 루트 노드 삭제

1.  

Heap의 성능

삽입/삭제 모두 최악의 경우 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. O(log n)