[알고리즘/자료구조] 힙(이진 힙)

0. 🔖 목차

1. 힙
   1-1 힙 개념
   1-2 삽입
   1-3 삭제

1. 힙

1-1. 힙 개념

부모 노드의 값이 자식 노드의 값보다 항상 큰 완전 이진 트리를 힙, 그중에서도 최대 힙이라고 한다. 만약 값이 항상 작다면 최소 힙이라고 한다.

형제 노드 사이의 대소 관계는 상관 없다.

1-2. 삽입

위 과정은 8, 4, 1, 6, 12, 3을 순서대로 힙에 삽입하는 과정이다.
혹은 [8, 4, 1, 6, 12, 3] 리스트 내에서 힙 구조로 정렬하는 과정이라고 볼 수도 있다.

힙에서 데이터를 삽입하는 과정은 아래와 같다.
1. 완전 이진 트리를 만족하도록 맨 마지막 노드에 추가할 값을 넣는다.
2. 힙의 성질을 만족하도록 부모 노드와 교환한다.
3. 더이상 교환할 수 없을 때 까지 2를 반복한다.

1-3. 삭제

힙에서 데이터를 삭제하는 과정은 아래와 같다.
1. 삭제할 노드를 제거하고 그 자리에 힙의 제일 마지막 노드 값을 넣는다.
2. 힙의 성질을 만족하도록 자식 노드와 교환한다.
3. 더이상 교환할 수 없을 때 까지 2를 반복한다.