[TIL] 자료구조 - 힙:추가와 제거

※ 힙: 추가와 제거

- 힙에 새로운 데이터를 추가하거나 제거할 때 힙의 규칙을 지켜야 한다. 최대 힙이면 부모 노드가 자식 노드보다 커야 최소 힙은 자식 노드가 부모 노드보다 커야한다.

 

노드 추가

1. 비어있는 공간에 노드 추가

2. 부모 노드보다 큰 숫자인지 확인 후 참인 경우 두 노드의 위치를 바꾼다. (trickle up)

 

루트 제거

1. 루트를 제거한다

2. 트리의 마지막 요소를 루트에 넣어준다

3. 루트에서 시작해 두 자식 중 큰 노드와 바꿔 힙의 규칙을 만족하게 한다. (tricle down)

 

무언가를 제거할 때 힙에선 항상 루트를 제거해주어야 한다.