힙 추가와 제거

들어가기 전에

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

 

학습 목표

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

 

핵심 단어

• 힙
• 최대 힙과 최소 힙

 

힙:추가와 제거

 

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

 

노드 추가

 

 

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) 루트를 제거할 때, 트리의 마지막 요소를 루트 자리에 넣어주는 이유는 무엇인가요?

 

나의 생각 : 루트가 비어있으면 힙 규칙에 위반되기 때문에 넣어준다.

 

 

출처 : https://www.boostcourse.org/cs204/lecture/626043?isDesc=false