비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산

 

히프(Heap)란?

히프는 완전 이진트리의 한 종류입니다. 이때 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 구조를 말합니다.

왼쪽은 기타 이진 트리, 오른쪽은 완전 이진 트리

히프는 모든 부모 노드가 그 자식 노드의 값보다 더 큰(혹은 작은) 값을 가지는 구조로 여러 값들 중 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만들어졌습니다. 이러한 히프는 최대 히프와 최소 히프로 나뉩니다.

여기서 최대 히프냐 최소 히프냐에 따라 루트 노드만 탐색하면 최댓값 혹은 최솟값을 O(1)의 시간복잡도로 얻어낼 수 있습니다. 또한, 이 히프 구조는 우선순위 큐를 구현할 때 많이 사용되기도 합니다.

 

• 최대 히프

최대 히프란 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 말합니다.

이때 같은 레벨에 있는 노드끼리는 비교하지 않습니다.

 

아래 그림에서 살펴보면 루트 노드인 9가 자식 노드인 8, 6보다 값이 크고 부모 노드 8은 자식 노드 7, 1보다 큽니다.

또한 같은 레벨에 있는 7, 1끼리는 서로 비교하지 않기 때문에 영향이 없습니다.

4, 1처럼 서로 부모-자식 관계가 아닌 노드일 때도 비교하지 않습니다.

• 최소 히프

최소 히프는 최대 히프와 반대로 부모 노드가 항상 자식 노드보다 작거나 같은 구조를 말합니다.

최대 히프때와 마찬가지로 같은 레벨에 있는 노드끼리는 비교하지 않습니다.

또한 부모-자식 관계가 아닌 노드일 때도 비교하지 않습니다.

 

히프의 삽입, 삭제 연산

최대 히프와 최소 히프에 대해 알았으니 히프 구조가 있을 때 새로운 수를 집어넣거나 뺄 때 어떤 식으로 연산이 진행되는지 살펴봐야 합니다. 이를 위해 최대 히프에서의 삽입, 삭제 연산을 그림을 통해 설명드릴 겁니다. 최소 히프도 같은 맥락으로 연산이 진행될 것이기 때문에 최대 히프의 경우에 대해서만 알아보겠습니다.

 

• 삽입 연산

삽입 연산의 알고리즘은 다음과 같습니다.

 

1. 새로운 노드를 마지막 노드로 삽입

2. 부모 노드와 대소를 비교하여 위치 swap 여부 결정

3. 최대 히프의 조건을 만족할 때까지 swap 반복

4. 더 큰 값을 가지는 부모 노드가 더 이상 없다면 종료

 

이해를 돕기 위해 두 가지 예시를 준비해 봤습니다.

첫 번째 예시는 최대 히프 구조에 (6)이 새로 삽입되는 상황입니다.

두 번째 예시는 최대 히프 구조에 (10)이 새로 삽입되는 상황입니다.

방금 두 번째 예시의 경우는 새로 삽입된 노드가 루트 노드까지 도달했는데요.

이 경우가 비교와 이동 연산을 가장 많이 필요로 하는 최악의 경우입니다.

삽입 연산의 시간 복잡도는 O(log(n))입니다.

 

최대 히프에서의 삽입 연산이 어느 정도 이해가 되셨나요?

이제는 삭제 연산에 대해서 살펴볼 차례입니다.

 

• 삭제 연산

삭제 연산의 알고리즘은 다음과 같습니다.

 

1. 루트 노드 삭제

2. 가장 마지막 노드를 루트 노드로 이동

3. 두 개의 자식 노드 중 더 큰 값과 부모 노드와 비교

4. 해당 자식 노드가 부모 노드보다 더 클 경우 swap

5. 3번 과정으로 돌아가 반복

6. 더 작은 값을 가지는 자식 노드가 더 이상 없다면 종료

 

이번에도 예시를 통해 이해해 봅시다.

 

삭제 연산의 시간 복잡도 역시 O(log(n))입니다. 

예시에는 나와 있지 않지만 삭제 연산의 최악의 경우는 마지막 노드까지 내려가며 비교 및 이동 연산을 하는 경우입니다.

---

지금까지 히프(최대 히프, 최소 히프)와 삽입 및 삭제 연산에 대해 알아보았습니다. 히프 구조가 어떤 식으로 작동 되는지 여러 예시를 통해 살펴보았는데요. 다음 글에서는 백준 풀이와 함께 히프 구조를 코드로 구현하는 방법에 대해 다뤄보겠습니다.

>>다음 글 : https://nomadsjh.tistory.com/42

[백준] 11279번 최대 힙 문제 풀이/힙 자료구조(2)