힙 - 원소 추가하기, 원소 삭제하기

👀 힙이란?

👉 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

항상 최대의 값들이 필요한 연산을 할 때 힙을 사용합니다.

 

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.

다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.

그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠!

따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

(반대도 같은 원리입니다.)

참고로, 힙은 다음과 같이 최댓값을 맨 위로 올릴 수도 있고, 최솟값을 맨 위로 올릴수도 있습니다.

 

👀 최댓값 힙(Max Heap)에 원소 추가하기

 

👉 힙의 규칙
"힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 합니다."라는 규칙은 항상 지켜져야 합니다.

 

따라서 원소를 추가하거나 삭제 할 때도 위의 규칙이 지켜져야 합니다.

 

👉 원소를 추가 할 때는 다음과 같습니다.

 

1. 원소를 맨 마지막에 넣습니다.

2. 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2번 과정을 반복합니다.

 

👉 원소 추가하기의 시간 복잡도는?

완전 이진트리의 최대 높이의 시간 복잡도는 O(log(N))입니다.

그렇다면, 반복되는 최대 횟수도 O(log(N))입니다.

 

즉, 최댓값 힙의 원소 추가는 O(log(N))만큼의 시간 복잡도를 가진다는 걸 알 수 있습니다.

 

👀 최댓값 힙(Max Heap)에 원소 삭제하기

 

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것입니다!

 

스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없습니다!

또한 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 합니다!

 

👉 원소를 삭제 할 때는 다음과 같습니다

 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교합니다.

두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3번 과정을 반복합니다.

5. 2번에서 제거한 원래 루트 노드를 반환합니다.

 

👉 원소 삭제하기의 시간 복잡도는?

 

완전 이진트리의 최대 높이의 시간 복잡도는 O(log(N))입니다.

그렇다면, 반복되는 최대 횟수도 O(log(N))입니다.

 

즉, 최댓값 힙의 원소 삭제는 O(log(N))만큼의 시간 복잡도를 가진다는 걸 알 수 있습니다.