들어가기 전에

힙에서 새로운 데이터를 추가하거나 제거하는 방법에 대해 살펴보도록 하겠습니다.

학습 목표

힙에서 노드를 추가하거나 제거하는 방법을 설명할 수 있습니다.

핵심 단어

• 힙
• 최대 힙과 최소 힙

강의 듣기

힙:추가와 제거

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

노드 추가

Add:

insert next available space

tricke up

1. 비어있는 공간에 노드를 추가합니다.
2. 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꿉니다. (trickle up)

루트 제거

Remove:

remove the root

replace w/ last element

tricle down

 - swap with the large of the children

1. 루트를 제거합니다.
2. 트리의 마지막 요소를 루트에 넣어줍니다.
3. 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족하게 합니다. (trickle down)

무언가를 제거할 때 힙에서는 항상 루트를 제거해야 합니다.

생각해보기

1) 루트를 제거할 때, 트리의 마지막 요소를 루트 자리에 넣어주는 이유는 무엇인가요?