[Data Structure] Heap

Heap

---

Heap은 최솟값, 최댓값을 빠르게 찾기 위해 고안된 자료구조이고, 무엇인가를 차곡차곡 쌓아 놓은 더미와 비슷하다 하여 Heap이라고 부른다. Heap은 '이진 트리'이되 '완전 이진 트리이다. '이진 트리'란 각 노드가 자식 노드를 최대 두개까지 가질 수 있는 트리를 말하며 '완전 이진 트리'란 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리를 말한다. 탐색보다는 삽입과 삭제에 최적화된 자료구조이다.

 

Array, Linked List에서 데이터 저장의 시간 복잡도는 O(n)이지만, Heap은 O(logn)이라는 좋은 성능을 보여준다. 그 이유는 Heap에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가하기 때문에, 데이터의 수가 두 배 늘 때마다 비교연산의 횟수가 1회 증가하기 때문이다. 따라서, Heap은 트리의 높이에 해당하는 수만큼의 비교연산만으로 데이터의 삽입, 삭제를 수행할 수 있다.

 

✅ Max Heap과 Min Heap

Heap은 루트 노드로 올라갈 수록 저장된 값이 커지는 Max Heap과 작아지는 Min Heap으로 나누어진다. 그림을 보면 딱 봐도 탐색이 쉽지 않을 것 같다는 느낌을 받을 수 있다. 또한, Heap은 Array를 이용해 구현하는 것이 원칙이다. Linked List를 이용하면 새로운 노드를 Heap의 마지막 위치에 추가하는 것이 쉽지 않기 때문이다. 아래는 Max Heap과 Min Heap의 예시이다.

 

 

✅Heap에서의 데이터 삽입

Max Heap을 예로 들면, Heap에서의 데이터 삽입은 새로운 데이터의 값이 가장 작다는 가정 하에 '마지막 위치'에 저장한다. 이 후,  적합한 위치를 찾을때까지 부모노드와 값을 비교하여 위치를 바꾸는 과정을 반복한다. 예시로, 위 Max Heap에 8을 넣어 데이터 삽입 과정을 살펴보자. 8을 '마지막 위치'삽입해 부모 노드인 6의 값과 비교한다. Max Heap이기 때문에 8과 6의 위치가 바뀌게 된다.

 

그 다음 다시, 8과 부모 노드인 12의 값을 비교한다. 8이 12보다 작기 때문에 현재 위치를 유지하며 삽입 과정이 마무리된다.

 

 

✅ Heap에서의 데이터 삭제

삽입 과정과 같이 Max Heap을 예로 들어보겠다. Heap에서의 데이터 삭제는 '마지막 위치'의 노드를 루트 노드의 자리로 옮긴 후, 적합한 위치를 찾을때까지 자식 노드와 값을 비교하는 과정을 반복한다. 예시로, 위 Max Heap의 루트 데이터를 삭제하는 과정을 살펴보자. 먼저, 루트노드를 삭제한 후 '마지막 위치'의 노드인 5을 루트노드의 자리로 이동시킨다.

 

 

5를 루트노드에 위치시켰으면 왼쪽, 오른쪽 자식노드와의 값을 비교한다. 12, 11이 모두 5보다 크기 때문에 둘 중 더 높은 12와 위치를 바꾼다. 값이 더 높은 노드와 위치를 교환하는 이유는 Max Heap의 조건을 만족해야하기 때문이다.

 

이 후, 다시 왼쪽, 오른쪽 자식노드와의 값을 비교한다. 5보다 큰 값은 6이기 때문에 6과 위치를 바꾼다. 더이상 조건을 만족하는 자식 노드가 없기 때문에 삭제 과정을 마무리한다.

 

 

Heap 활용

---

✅ Heap 자료구조의 활용

Heap은 삽입과 삭제에서 강점을 보이기 때문에 작업 스케줄링, 네트워크 트래픽 제어와 같은 작업에 활용할 수 있다고 한다. Heap을 사용하는 알고리즘으로는 Heap Sort, Priority Queue와 Dijkstra와 같은 그래프 알고리즘에 사용된다고 한다.

 

✅ Java 에서 Heap 사용하기

Java Collection에는 아쉽게도 Heap이 없다. 하지만, Priority Queue를 이용하여 Min-Max Heap의 매커니즘을 동일하게 이용할 수 있다. Java에서 Heap을 사용하는 방법이 궁금하다면 아래 Priority Queue에 대한 게시물을 보시기 바랍니다.

 

 

[Algorithm] Priority Queue