반응형
힙(Heap)
힙(Heap)의 개념
- 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조이다.
- 여러 개의 값 중 최대, 최소를 빠르게 찾기 위해 만들어진 자료구조이다.
힙의 종류
- 최대 힙(Max Heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다. // Key(부모 노드) >= Key(자식 노드)
- 최소 힙(Min Heap)
: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다. // Key(부모 노드) <= Key(자식 노드)
힙의 구현
- 힙의 데이터를 저장하는 자료구조는 배열을 이용한다.
- 힙에서 부모 노드와 자식 노드는 특별한 관계를 가진다.
왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) X 2
오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) X 2 + 1
부모 노드의 인덱스 = (자식 노드의 인덱스) / 2
힙의 삽입
- 힙의 삽입 방법
1. 힙에 새로운 노드는 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환하여 힙의 성질(최대 힙, 최소 힙)을 만족시키도록 반복한다.
- 힙의 삽입 예시(최대 힙)
힙의 삭제
- 힙의 삭제 방법
1. 루트 노트를 삭제한다.
2. 힙의 마지막 노드를 루트 노드로 가져간다.
3. 루트 노드와 자식 노드들을 비교하며 힙의 성질을 만족시키도록 반복한다.
- 힙의 삭제 예시(최대 힙)
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
정렬 알고리즘 - 퀵 정렬(Quick Sort) (0) | 2020.06.16 |
---|---|
정렬 알고리즘 - 병합 정렬(Merge Sort) (0) | 2020.06.16 |
정렬 알고리즘 - 삽입 정렬(Insertion Sort) (0) | 2020.06.14 |
정렬 알고리즘 - 선택 정렬(Selection Sort) (0) | 2020.06.11 |
정렬 알고리즘 - 버블 정렬(Bubble Sort) (0) | 2020.06.08 |
댓글