[Swift] Array를 이용한 Heap 구현 1 - 개요

해당 포스팅에 앞서 트리에 대한 전반적인 정리는 이전 포스팅(https://taeminator1.tistory.com/42)을 참고하면 된다. 

 

힙은 단말 노드가 아닌 각각의 노드에 대해 노드의 값이 자식 노드의 값과 비교해 일정한 규칙을 갖는 완전 이진 트리이다. (노드의 값(키)은 중복이 가능하다) 힙은 대표적으로 최대 힙과 최소 힙이 있는데, 자식 노드의 값이 부모 노드의 값 보다 크지 않은 힙을 최대 힙(Max Heap), 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 최소 힙(Min Heap)이라고 한다. 이번 포스팅에서는 특별한 언급이 없다면 최대 힙(각각의 부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우)으로 가정하고 힙에 대한 설명을 이어 나가겠다. 

 

힙의 가장 큰 특징은 반정렬 상태를 유지하는 자료 구조라는 것이다. 자식 노드의 값 간에는 제약이 없기 때문에 완전히 정렬되지는 않지만, 자식 노드들의 값은 부모 노드의 값보다는 크지 않아야 한다는 조건 때문에 어느 정도 정렬이 되어 있어 "반정렬"이라는 용어를 사용했다. 이와 비교해, 이진 탐색 트리는 부모 노드와 왼쪽, 오른쪽의 자식 노드의 상호 간의 제약이 있기 때문에 완전한 정렬 상태를 유지한다고 할 수 있다. 이러한 Heap도 자료 구조의 일종이기 때문에, 필수적인 연산이 있다. 다음 포스팅에서 이러한 연산들을 직접 구현해 볼 텐데, 이때 앞서 설명한 "반정렬"상태를 유지하는 것이 핵심이다. 

 

힙도 다양한 방식으로 구현할 수 있는데, 큐(Queue)나 리스트(List)에서는 연결 리스트(Linked List)를 이용하여 구현한 것과 달리 배열을 이용하여 구현하고자 한다. 힙 자체가 와전 이진 트리의 일종이기 때문에 부모 노드와 자식 노드 간의 관계를 파악하면, 원하는 데이터에 바로 접근할 수 있어서 연결 리스트에 의해 연결된 노드를 찾는 것보다 쉽게 구현할 수 있고, 힙의 상태를 유지하기 위해 연산 시에 자료의 이동이 많은데, 배열로 구현할 경우, 해당 원소의 값만 바꾸어주면 되지만 연결 리스트로 구현할 경우, 연결된 노드들을 매번 새로 갱신해 줘야 하는 불편함이 있기 때문이다. 

 

배열은 선형적인 자료구조이고, 힙은 계층적인 자료구조이기 때문에 둘 간의 관계를 확인해볼 필요가 있다. 각각의 노드의 위치를 배열의 인덱스에 대응시킨 아래의 완전 이진 트리를 살펴보자. 루트 노드를 시작으로 레벨에 대한 위치에 따라 배열의 인덱스가 순서대로 결정된다. 

완전 이진 트리의 노드의 위치에 따른 배열의 인덱스

눈여겨볼 점은 배열의 인덱스는 부모와 자식 노드 간의 관계가 아래와 같이 성립한다는 것이다. 

• 보모 노드의 인덱스 = (왼쪽 또는 오른쪽 자식 노드의 인덱스 - 1) / 2
• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 2

다음 포스팅에서 Swift를 이용하여 실제로 힙을 구현해 보도록 하겠다.