728x90
반응형
힙(heap)
- 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조
- 최대 힙(max heap)
ㄴ 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리
ㄴ 부모 노드 키 값 ≥ 자식 노드 키 값
ㄴ 루트 노드 : 키 값이 가장 큰 노드
- 최소 힙(min heap)
ㄴ 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리
ㄴ 부모 노드 키 값 ≤ 자식 노드 키 값
ㄴ 루트 노드 : 키 값이 가장 작은 노드
힙 삽입 연산
1단계 : 완전 이진트리를 유지하면서 노드를 확장하여, 삽입할 원소를 임시 저장
ㄴ 노드가 n개인 완전 이진트리에서 다음 노드의 확장 자리는 n+1번의 노드
ㄴ n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장
2단계 : 만들어진 완전 이진트리 내에서 삽입 원소의 자리 찾기
ㄴ 현재 위치에서 부모 노드와 비교하여 크기 관계 확인
ㄴ 현재 부모 노드의 키 값 ≥ 삽입 원소의 키 값 관계가 성립하지 않으면, 현재 부모 노드의 원소와 삽입 원소의 자리를 서로 바꿈
힙 삭제 연산 : 루트 노드의 원소만 삭제 가능
1단계 : 루트 노드의 원소를 삭제하여 반환
2단계 : 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진트리로 조정
ㄴ 노드가 n개인 완전 이진트리에서 노드 수 n-1개의 완전 이진트리가 되기 위해 마지막 노드(n번 노드) 삭제
ㄴ 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장
3단계 : 완전 이진트리 내에서 임시 저장된 원소의 자리 찾기
ㄴ 현재 위치에서 자식 노드와 비교하여 크기 관계 확인
ㄴ 임시저장 원소의 키 값 ≥ 현재 자식 노드의 키 값 관계가 성립하지 않으면, 현재 자식 노드의 원소와 임시 저장 원소의 자리를 서로 바꿈
순차 자료구조를 이용한 히프의 구현
- 부모 노드와 자식 노드를 찾기 쉬운 1차원 배열의 순차 자료구조 이용
728x90
반응형
'자료구조' 카테고리의 다른 글
| [자료구조] 그래프(Graph) 순회 (0) | 2022.01.23 |
|---|---|
| [자료구조] 그래프(Graph)의 구현 (0) | 2022.01.23 |
| [자료구조] 이진 탐색 트리 Binary Search Tree (0) | 2022.01.16 |
| [자료구조] 수식의 표기법 (Notation) (0) | 2022.01.09 |
| [자료구조] 큐(Queue) (0) | 2022.01.09 |