Heap
완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조
1. 최대 힙(Max heap)
키값이 가장 큰 노드를 찾기 위한 완전 이진 트리
부모 노드의 키값 > 자식 노드의 키값
루트 노드 : 키값이 가장 큰 노드
2. 최소 힙(Min heap)
키값이 가장 작은 노드를 찾기 위한 완전 이진 트리
부모 노드의 키값 < 자식 노드의 키값
루트 노드 : 키값이 가장 작은 노드
삽입 연산
최대힙이기 때문에 정렬이 필요할 경우 해야함.
삭제 연산
1. 힙에서는 루트 노드의 원소만을 삭제할 수 있음
2. 루트 노드의 원소만을 삭제하여 반환
3. 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있음. 이를 이용하여 우선순위 큐를 힙으로 구현할 수 있음.
참고 SW expert academy
반응형
'Computer science > Algorithm' 카테고리의 다른 글
| Counting Sort (0) | 2021.02.16 |
|---|---|
| Bubble-Sort (0) | 2021.02.16 |
| Binary search Tree (0) | 2021.02.04 |
| 이진 트리 (0) | 2021.02.03 |
| Tree (0) | 2021.02.03 |