Heap

---

Heap 자료구조는 완전 이진트리의 한 종류로 중복값을 허용하며, 최대값과 최솟값을 빠르게 찾을 수 있다는 장점이 있다.

Heap 자료구조를 종류별로 알아보자

MinHeap(최소 힙)

부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전이진트리형 자료구조이다. 아래 이미지는 MinHeap의 Sample 데이터이다.

MinHeap의 삽입 과정은 아래와 같다.

1. 새로운 요소가 Add되면 마지막 노드에 삽입한다.
2. 새로운 노드가 부모 노드보다 크면 Swap한다.
3. 1~2번 과정을 모든 부모노드가 각 자식노드보다 작아질때까지 반복한다.

MinHeap의 삭제 과정은 아래와 같다.

1. root 노드를 제거한다.
2. 마지막 노드를 root 노드로 이동시킨다.
3. root 노드와 왼쪽 자식 노드, 오른쪽 자식노드중 큰 키값을 가진 자식노드와 비교하여, root 노드의 키값이 클 경우 swap한다.
4. 1~3번 과정을 모든 부모노드가 각 자식노드보다 작아질때까지 반복한다.

MaxHeap(최대 힙)

부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전이진트리형 자료구조이다. 아래 이미지는 MaxHeap의 Sample 데이터이다.

MaxHeap의 삽입 과정은 아래와 같다.

1. 새로운 요소가 Add되면 마지막 노드에 삽입한다.
2. 부모노드가 새로운 노드보다 작으면 Swap한다
3. 1~2번 과정을 모든 부모노드가 자식노드보다 클때까지 반복한다.

MaxHeap 삭제 과정은 아래와 같다.

1. root 노드를 제거 한다.
2. 마지막 노드를 root 노드로 이동한다.
3. root 노드와 왼쪽 자식 노드, 오른쪽 자식노드중 작은 키값을 가진 자식노드와 비교하여, root 노드의 키값이 작을  경우 swap
4. 1~3번 과정을 모든 부모노드가 자식노드보다 클때까지 반복한다.

---

연결문서