C로 만드는 자료구조- 힙(Heap)이란?

힙 (Heap)이란?

 힙은 이진 트리의 하나이다. 힙의 특징은 루트 노드가 언제나 그 트리의 최댓값 또는 최솟값을 가지는 것이다. 힙의 루트 노드가 최댓값을 가지면 최대 힙, 최솟값을 가지면 최소 힙이라고 한다. 최대 힙은 모든 부모 노드가 자식 노드보다 큰 값을 가지느 최대 트리의 특성을 가지고 있고 최소 힙은 모든 부모 노드가 자식 노드 보다 작은 값을 가지는 최소 트리의 특징을 가지고 있다. 마지막으로 힙은 항상 완전 이진 트리이다.

힙이 되기 위한 조건을 정리하면 아래와 같다.

1. 완전 이진 트리여야 한다.
2. 최대 트리 혹은 최소 트리의 특징을 가진다.

아래는 최대 힙과 최소 힙의 예시이다.

두 개의 이진 트리 모두 완전 이진 트리이며 최대 힙은 모든 부모 노드가 자식 노드의 값보다 크기 때문에 최대 트리의 성질을 가지고 최소 힙또한 모든 부모 노드가 자식 노드의 값보다 작기 때문에 최소 트리의 성질을 가지기 때문에 두개의 이진 트리는 모두 힙이라고 할 수 있다.

힙의 추상 자료형

힙 사용에 필요한 기본 연산을 정리한 힙의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름		입력	출력	설명
힙 생성	createHeap()	힙의 크기 n	힙 H	최대 n개의 원소를 가질 수 있는 힙 H 생성
힙 삭제	deleteHeap()	힙 H	N/A	힙 메모리 해제
노드 추가	inseertHeap()	힙 H 원소 e	성공/실패 여부	힙에 새로운 원소 추가
노드 제거/반환	deleteHeapNode()	힙 H	원소 e	힙의 루트 노드 제거 후 반환

 힙의 새로운 자료를 추가하거나 자료를 제거하고 반환하는 2가지 연산만 존재한다. 자료를 반환하는 경우 특정 자료를 반환 하는 것이 아닌 무조건 루트 노드를 반환 한다. 따라서 자료를 반환 한다는 것은 최대 힙에서는 언제나 최댓값이 반환되고 최소 힙에서는 최솟 값이 반환 된다.

※본 글에서는 최대 힙에서의 연산 방법과 구현만을 다룰 예정 입니다.

3. 최대 힙에서의 삽입 연산

 최대 힙에서의 삽입 연산은 크게 2가지로 나뉜다.

- 1단계: 트리의 마지막 자리에 임시 저장 

 힙의 새로운 노드를 추가 하면 일단 임시적으로 트리의 가장 마지막 자리에 저장한다. 힙은 완전 이진 트리 형태이기 때문에 임시 저장된 자리는 어떻게든 채워줘야 하기 때문이다. 

삽입 연산 1단계

그림과 같이 새로운 노드 11을 추가 하기 위해서 일단 새로운 노드를 완전 이진 트리의 마지막 자리에 임시로 저장을 해준다.

- 2단계: 부모 노드와 키 값 비교 및 이동

  앞 단계에서 새로운 노드를 완전 이진 트리의 마지막 자리에 임시로 저장 했을 때 운이 좋다면 최대 트리의 특징 그래도 유지 하겠지만 그렇지 않을 경우가 더 많을 것이다. 따라서 최대 트리의 특징을 가지기 위해 새로운 노드값과 그 부모 노드의 값을 비교한다. 만약 새로운 노드 값이 더 크다면 부모 노드와 자리를 바꾸고 새로운 노드는 바뀐 위치에서의 부모 노드와 한번 더 값을 비교하여 자리 교환 여부를 결정한다. 이 과정은 새로운 노드가 새로운 노드보다 큰 값을 만나거나 만나지 못해 루트노드에 도달 할때 까지 반복한다.

삽입 연산 2단계

 그림과 같이 앞단계에서 임시 저장한 새로운 노드 11을 부모 노드인 7과 비교 했을 때 새로운 노드가 더 크기 때문에 자리를 맞 바꾼다. 그 후에 한번 더 바뀐위치에서의 부모 노드(15)와 새로운 노드(11)를 비교 했을 때 부모 노드(15)가 더 크기 때문에 자리는 그댈 유지하고 연산을 멈춘다. 

4. 최대 힙에서의 삭제 연산

 최대 힙에서의 삭제 연산은 크게 3가지로 나뉜다.

- 1단계: 루트 노드의 삭제 

 앞서 말했듯이 힙에서의 삭제 연산은 무조건 루트 노드를 대상으로 한다. 따라서 삭제 연산에서 가장 먼저 루트 노드를 힙에서 제거 해준다.

삭제 연산 1단계

  그림과 같이 최대 힙에서 최댓 값을 가지는 루트 노드(15)를 제거한다.

- 2단계: 트리 마지막 자리 노드의 임시 이동

  앞단계에서 루트 노드를 제거했기 때문에 이제 그 빈자리를 채워주어야 한다. 그 빈자리를 일단 완전 이진 트리의 마지막 위치의 노드를 이동 루트 노드를 이동시켜 임시로 저장한다. 어짜피 힙은 완전 이진 트리를 유지해야 하기 때문이다.

삭제 연산 2단계

  그림과 같이 루트 노드의 빈 자리를 채우기 위해 마지막 자리의 위치한 노드 7을 루트 노드 자리에 임시로 저장했다.

- 3단계: 자식 노드와 키 값 비교 및 이동

 힙에서의 삽입 연산 때와 마찬가지로 임시로 루트 노드에 저장된 노드가 운이 좋다면 최대 트리의 특징을 만족하지만 만족하지 않는 경우가 훨씬 많을 것이다. 따라서 최대 트리의 특징을 유지하기 위해 자식노드와 비교하여 루트 노드보다 큰 값이 있다면 자리를 바꿔주는 것을 반복한다. 이때 2개의 자식 노드가 둘 다 값이 더 크다면 2개의 자식 노드중 더 큰 값과 자리를 바꿔주어야 최대 트리의 특징을 유지 할 수 있다.

루트 노드에 임시 저장된 7을 자식 노드인 5,11과 비교 후 더 더 큰값임 11과 자리를 바꾼다. 바꾼후 다시 자식노드인 9와 비교 후 다시 자리를 바꿔준다.

다음 글에서는 실제로 배열을 이용하여 힙을 구현을 해볼 것이다.