Heap

Heap이란?

힙은 따라야 하는 몇 가지 추가 규칙이 있는 이진 트리이다. 이 두 가지 규칙이 힙을 다른 트리 구조와 구별하는 요소를 정의하는 속성이다. 그 속성은 트리의 모양과 노드의 순서이다. 

먼저 모양이다. 이진 트리가 힙이 되려면 완전 트리여야한다. 완전 트리는 트리의 마지막 level을 제외하고는 노드들이 다 채워져 있어야한다. 그리고 트리의 마지막 level에서는 항상 맨 왼쪽 노드가 먼저 채워져야한다.

순서의 규칙은 부모 노드는 자식 노드의 값보다 크거나 같아야 하거나 자식 노드의 값보다 작거나 같아야 한다. 이 두 형식의 순서에 따라서 힙이 분류된다. 최소 힙(min heap)은 루트 포함 모든 상위 노드가 하위 노드보다 값이 작거나 같은 경우이다. 결국 최소 값이 루트 노드가 되는 것이다. 최대 힙(max heap)은 이 반대이다. 루트 포함 모든 상위 노드가 하위 노드보다 값이 크거나 같아서 루트가 최대 값이 되는 것이다.

여기서 주목해야할 사항은 첫째, 항상 힙은 중복 값을 가질 수 있다. 둘째, 힙은 이진 검색 트리의 규칙을 따르지 않는다. 즉, 왼쪽 노드가 오른쪽 노드보다 작을 필요가 없다. 자식 노드의 순서는 힙에선 중요하지 않다.

Heap을 사용하는 방법

힙을 늘리고 줄이는 것부터 알아보자. 힙을 늘리거나 줄일때는 속성을 잘 생각해야하는 것이다. 항상 힙의 모양과 구조를 유지해야한다. 힙을 키울 땐 트리에서 가장 왼쪽에 있는 사용 가능한 지점에 노드를 추가할 수 있다. 즉, 마지막 level에서 가장 왼쪽에 있는 노드이다. 값을 추가했다면 노드의 순서에 대한 속성을 살펴봐야한다. 노드의 순서를 위반할 경우, 순서가 잘못된 두 노드를 교환하면 된다. 이것을 bubble up이라고 한다. 우리가 버블 정렬을 하면 계속 위치를 바꾸면서 소팅을 하는 것처럼 여기서도 하나하나 노드를 계속 바꾸면서 위치를 찾아간다. 힙을 줄일땐 작업을 수행하면서 힙의 모양과 순서 속성을 어기면 안되기 때문에 살짝의 변형된 작업을 해야한다. 아까 힙을 키우면서 순서 속성을 어기지 않기 위해 우리는 스왑함으로써 속성을 유지했다. 그리고 대부분의 힙에서 제거는 루트 노드를 제거한다. 루트 노드가 최대 값 혹은 최소 값이기 때문이다. 따라서 루트 노드를 제거한다고 가정해보자. 루트 노드를 제거하면 모양이 어긋난다. 그렇기에 마지막 level에서 맨 오른쪽 노드가 마지막으로 추가된 노드이기에 해당 노드를 루트로 옮긴다. 그리고 이 노드의 위치를 찾아서 자식 노드와 비교하면서 자식 노드 둘 중 더 큰 값 혹은 더 작은 값과 스왑을 하면서 자신의 위치를 찾아간다. 그러면 순서의 속성 또한 유지된다. 이를 bubble down이라고 한다.

 

힙에 대해 알아보고 작동 방식에 대해서도 알아봤다. 그렇다면 힙을 구현하는 방법과 왜 그렇게 구현해야는지를 생각해보자.

Heap을 구현하는 방법

힙을 링크드 리스트를 이용해서 구현을 할 수 있다 하지만 더 흥미로운 방법은 배열이다. 힙은 부분적으로 정렬된 자료구조이다. 하지만 이진 검색 트리와 같이 완전히 정렬되지는 않는다. 힙의 가장 중요한 특성은 최대값 혹은 최소값 요소가 항상 루트 노드라는 것이다. 이 특성은 배열에서 가장 첫번째 인덱스로 나타낼 수 있다. 항상 0 인덱스에 루트 노드가 위치하는 것이다. 루트 노드의 인덱스를 알고 있으면 해당 힙의 동일한 배열 표현 내에서 자식 노드가 위치할 위치를 결정하기 위해 인덱스 조작이 가능하다는 것이다. 부모 노드의 인덱스가 i라면 왼쪽 자식은 항상 2 x i + 1 이고 오른쪽 자식은 항상 2 x i + 2이다. 또 현재 인덱스의 부모 인덱스는 (i - 1)/2 가 된다. 3/2 = 1.5 지만 이를 올림해준다.

Heap을 배열로 구현하는 이유

Queue 때문이다. 큐는 되게 많이 실생활에서 사용될 수 있고 CPU 스케줄링 등에서 사용도 가능하다. 힙은 우선 순위 큐를 나타내는 매우 효율적인 방법이다. 만약 힙을 링크드 리스트로 구현한다면 큐처럼 양쪽 방향에서의 접근이 필요한데 마지막 요소로 가기위해선 링크드 리스트는 O(N)의 시간 복잡도를 요구하기에 배열로 구현하는 것이 훨씬 효율적이다는 것이다. 

 

참조  - 참조된 링크엔 이미지가 있어 이해하기 더 용이합니다.

- https://medium.com/basecs/learning-to-love-heaps-cef2b273a238

Learning to Love Heaps