힙 자료구조
최솟값 또는 최댓값을 루트노드로 가지는 완전이진트리 형태의 자료구조
완전이진트리
마지막 노드를 제외한 모든 노드들이 2개의 자식을 갖으며, 마지막 노드의 자식은 왼쪽부터 채워지는 트리
힙 종류
- 최소 힙(Min Heap) : 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전이진트리
- 최대 힙(Max Heap) : 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전이진트리
삽입
44, 33, 77, 11, 55, 88 을 삽입하는 과정을 살펴보자.
// 1단계
44
// 2단계
44
/
33
// 3단계
44 77
/\ /\
33 77 33 44
// 4단계 ~ 5단계
77 77
33 44 55 44
11 55 11 33
// 6단계
77 88
55 44 55 77
11 33 88 11 33 44삭제
삭제를 할 때는 항상 루트 노드가 삭제되고 이 자리는 맨 마지막 노드와 교체된다.
// 1단계
88
/\
55 77
/\ /
11 33 44
// 2단계
44
/\
55 77
/\
11 33
// 3단계
77
/\
55 44
/\
11 33시간 복잡도
- 삽입 : O(log N)
- 삭제 : O(log N)