[자료구조] Heap

Heap이란

완전 이진 트리 기반의 자료구조이다.

* 완전 이진 트리  :  마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있는 형태

여러 값들 중 최소값과 최대값 탐색에 특화되어 있다. 그렇기에 힙은 정렬된 상태가 아니다.

힙 트리에서는 중복값을 허용한다. (이진 탐색 트리는 중복 허용 x)

 

 

힙의 종류

1.  최대 힙 (Max Heap)

 

부모 노드 ≥ 자식 노드 → 루트가 최댓값

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

 

 

 

2. 최소 힙 (Min Heap)

 

부모 노드 ≤ 자식 노드 → 루트가 최솟값

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

 

힙의 구현

힙은 배열 기반으로 이루어져 있다.

힙의 인덱스는 위에서 부터 아래로 내려오고 왼쪽에서 오른쪽으로 가면서 증가한다.

 

 

힙의 삽입

 

 

 

 

 

힙의 삭제

 

힙의 삭제는 항상 맨 앞에 노드 (루트 노드)에서 일어난다.

 

 

힙의 시간복잡도

insert (삽입)	O(log n)	새 요소를 마지막에 넣고 위로 올라가며(heapify up) 위치 조정
delete (삭제)	O(log n)	루트 제거 후 마지막 요소를 루트에 넣고 아래로 내려가며(heapify down) 위치 조정
peek (최상단 확인)	O(1)	heap[0] 접근만 하므로 상수 시간
build heap (n개로 초기 힙 만들기)	O(n)	heapify를 아래에서 위로 실행하면 선형 시간 가능

 

힙은 완전 이진 트리라서 높이 = log₂(n) 수준이다.