트리(3) | 히프
출처 : book.naver.com/bookdb/book_detail.nhn?bid=10896666
C로 배우는 쉬운 자료구조
단계별 그림과 삽화로 이론을 다지고 C 언어로 구현해 보는 자료구조 입문서 자료를 구조화하는 다양한 방법을 단계별 그림과 삽화를 곁들여 쉽게 설명하고, 자료구조의 핵심 알고리즘을 C 프로
book.naver.com
목차
01 트리에 대해
02 이진트리에 대해
03 이진트리의 구현과 순회
04 이진탐색트리, AVL 트리
05 히프
05. 히프
◆ 히프 : 완전이진트리에 있는 노드 中 키값이 가장 크거나 가장 작은 노드 찾기 위해 만든 자료구조
▶ 최대히프 : 키값 가장 큰 노드 찾기 위한 완전이진트리
- {부모노드의 키값 >= 자식노드의 키값}
- 루트노드 : 키값이 가장 큼
보통 히프는 최대히프를 말함!
▶ 최소히프: 키값이 가장 작은 노드 찾기 위한 완전이진트리
- {부모노드의 키값 <= 자식노드의 키값}
- 루트노드: 키값 가장 작음
◇ 히프의 삽입연산
ⅰ) 완전이진트리조건 만족하도록 자리확장, 임시저장
- 노드 n개인 완전이진트리 → (n+1)번 노드 확장
ⅱ) 부모노드와 크기조건 만족하는 위치 찾기
- 현재위치에서 부모노드와 크기관계 확인
- {현재 부모노드의 키값 >= 삽입원소의 키값} 관계 성립 x → 자리 바꿈
◇ 히프의 삭제연산 - 루트노드의 원소만 삭제가능!
ⅰ) 루트노드 원소 삭제 → 노드수 (n-1)개로 줄어듬
ⅱ) 노드의 수가 (n-1)인 완전이진트리로 조정
- 마지막 노드(n번 노드) 삭제
- 삭제된 n번 노드에 있던 원소를 빈 루트노드에 임시저장
ⅲ) 자식노드와 크기조건 만족하는 위치 찾기
- 현재위치에서 자식노드와 크기관계 확인
- {임시저장 원소의 키값 >= 현재 자식노드의 키값} 관계 성립 X → 자리 바꿈
Q. 다음과 같은 키값을 가지는 원소들을 공백 히프에 차례대로 삽입하여 최대 히프를 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?
<공백히프에 차례로 삽입해 최대히프 생성>
<삭제연산>
