Heap 구조의 이해

 

 

Heap의 개념

 

 

Heap은 트리 구조 기반의 자료구조로서 일반적으로 배열로 구현되며, node 번호와 배열의 index가 일치한다. 최댓값 또는 최솟값을 빠르게 찾는 데 사용된다.

 

Heap은 추출 과정을 통해 최댓값 또는 최솟값을 삭제하고 반환하며, 추출 이후에도 Heap의 구조를 유지해야 한다. 또한 삽입 과정을 통해 마지막 node에 새로운 값을 삽입하며, 마찬가지로 Heap의 구조를 유지한다.

 

최댓값을 가지는 Heap은 max heap, 최솟값을 가지는 Heap은 min heap이라고 한다. max heap의 경우 부모 node의 우선순위가 자식 node의 우선순위보다 항상 크거나 같다. 반대로 min heap의 경우 부모 node의 우선순위가 자식 노드의 우선순위보다 항상 작거나 같다.

 

 

max heap에서 heap 구조를 유지하는 예시

 

 

최상위 node(root node)에서부터 최하위 node(leaf node)까지의 모든 계층에서 부모 node의 값은 자식 node의 값보다 크거나 같아야 한다.

 

왼쪽의 max heap 그림에서 부모 node의 값이 자식 node의 값보다 큰 것을 알 수 있다. 오른쪽 그림은 60을 삽입한 상황이다. 17의 자식 node에 삽입되지만 60은 부모인 17보다 큰 값이므로 17과 위치를 교체한다. 60은 root node의 값인 50보다도 크므로 다시 위치를 교체한다. 이로써 root node의 값은 60이 된다. data를 삭제하는 경우에도 마찬가지 메커니즘을 따른다.

 

이렇게 자리를 교체하는 방법에는 위에서 사용한 bottom-up 방식뿐만 아니라, 교체 순서에 따라 top-down 방식, reconstruction 방식 등이 있다.

 

min heap의 경우 반대로 root node부터 leaf node까지의 모든 계층에서 부모 node가 자식 node에 비해 항상 작거나 같은 값을 가지게 된다.

 

 

Heap 구조에서의 명칭

 

 

가장 상위의 node를 root node, 가장 하위의 node를 leaf node라고 한다. tree(나무)의 구조를 생각해 보면 root(뿌리)와 leaf(나뭇잎)의 관계가 이해하기 쉽다.

 

 

 

Heap의 응용

 

 

Heap은 완전 이진트리의 형태로서 최댓값과 최솟값 검색의 시간 복잡도는 O(1)이며, 삽입과 추출 모두 시간 복잡도가 O(log N)으로서 높은 효율성을 보인다. 따라서 성능적인 효과를 기대할 때뿐만 아니라 시간제한이 있는 코딩 테스트에서도 이진 탐색 트리(검색 시간 복잡도 O(log N))를 이용한 풀이에 비해 유리한 위치를 점할 수 있다.

 

Heap은 주로 data의 우선순위에 따라 항목을 저장하고 추출하는 자료구조인 우선순위 큐(priority queue)를 구현할 때 사용되며, O(log N)의 낮은 시간 복잡도를 기반으로 매우 효율적인 우선순위 큐를 구현할 수 있다.

 

Heap을 이용한 정렬 알고리즘인 Heap Sort에 사용된다.

 

다익스트라(Dijkstra) 등의 그래프 알고리즘을 구현할 때 Heap을 통해 더욱 효율적인 알고리즘을 구현할 수 있다.

 

Stack과 함께 Java 메모리의 주요 구성요소이며,  객체 생성 시 객체가 저장된다.