힙 트리 ( 최소 힙, 최대 힙 )

알고리즘 공부

transfer_kk 2023. 3. 1. 11:58

힙트리(heap)란?

최댓값 또는 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.

부모-자식 노드 간의 대소 관계가 성립하며 반정렬 상태(느슨한 정렬 상태)를 유지한다.

형제 간의 대소 관계는 없고 값을 중복하여 저장가능 하다

힙은 최대 힙의 높이만큼 탐색하여 O(logn)의 시간 복잡성을 가진다.

힙 트리는 최소 힙과 최대 힙으로 나뉠 수 있다.

최소 힙은 부모노드가 자식 노드보다 작거나 같으며

최대 힙은 부모노드가 자식 노드보다 크거나 같다.

힙 트리에서의 삽입 연산

1. 트리 끝에 노드를 추가한다.

2. 부모 노드와 대소를 비교한다.

3-1. 최대 힙인 경우, 추가한 값이 부모 노드보다 크면 자리를 바꾼다.

3-2. 최소 힙인 경우, 추가한 값이 부모 노드보다 작으면 자리를 바꾼다.

4. 3번을 반복한다.

힙 트리에서의 삭제 연산

1. 루트 노드에서 값을 제거한다.

2. 마지막 노드를 루트 노드로 옮긴다.

3. 자식 노드와 대소관계를 비교한다.

4-1. 최소 힙인 경우, 자식 노드 중에서 더 작은 노드와 부모 노드의 자리를 바꾼다.

4-2. 최대 힙인 경우, 자식 노드 중에서 더 큰 노드와 부모 노드의 자리를 바꾼다.

5. 4번을 반복한다.

참고한 사이트