[자료구조] - 힙(Heap)

 

 

 

힙(Heap)이란?

힙은 기본적으로 완전 이진 트리(Complete Binary Tree)이면서,

성질에 따라 최대 힙(Map Heap)과, 최소 힙(Min Heap), 두 가지 종류로 분류됩니다.

 

 

 

최대 힙 (Max Heap)

1. 완전 이진 트리(Complete Binary Tree)이면서
2. 각 노드의 Key 값이 자식 노드의 Key 값보다 작지 않다.

 

 

최초 힙 (Min Heap)

1. 완전 이진 트리(Complete Binary Tree)이면서
2. 각 노드의 Key 값이 자식 노드의 Key 값보다 크지 않다.

 

 

 

 

참고로 메모리 영영 중, 동적으로 메모리가 할당되는 영역은 대부분 힙 자료구조로 이루어져 있습니다.

 

 

 

 

 

 

 

 

 

 

 

힙에서의 삽입

최대 힙 기준으로 설명하겠습니다.

삽입하려는 노드를 가장 마지막에 추가합니다.

이로 인해 힙이 망가졌으므로 다음을 통해 복구합니다.

삽입된 노드 즉, Heap의 마지막 노드에서부터 다음을 반복합니다.

1. 부모 노드를 확인합니다.  만약 존재하지 않는다면 반복을 종료합니다.
2. 부모 노드가 존재한다면, 부모 노드보다 작거나 같은 경우 해당 위치가 올바르게 삽입된 위치이므로 반복을 종료합니다.
3. 만약 부모 노드보다 큰 경우 부모노드와 위치를 바꾼 후 다시 바꾼 위치의 부모 노드와 비교하는 작업을 반복합니다.

 

 

 

 

 

 

 

 

분석

루트의 레벨을 1로 보았을 때, n개의 노드를 갖는 완전이진트리의 높이는 다음과 같습니다.

$$[log \; n] + 1 $$

 

따라서 삽입을 위해 부모와 비교하는 작업을 반복하는 최대 횟수는 다음과 같습니다.

$$[log \; n] + 1 $$

 

즉 시간 복잡도는 다음과 같습니다.

$$O(log\;n)$$

 

 

 

 

 

 

 

 

 

 

 

힙에서의 삭제 (Root 노드 삭제)

최대 힙 기준으로 설명하겠습니다.

 

최대 힙에서의 Root를 삭제하는 것은 결국 최댓값을 삭제하는 것과 동일합니다.

루트 노드를 제거합니다.

이로 인해 힙이 망가졌으므로 다음을 통해 복구합니다.

Heap의 마지막 노드를 root의 위치로 가져옵니다.
이후 루트에서부터 다음을 반복합니다.

1. 자식이 존재하는지 확인합니다. 존재한다면 자식들 중 큰 값을 갖는 자식과 위치를 바꿉니다.
2. 자식이 존재하지만 자식의 값이 현재 값보다 작다면 반복을 종료합니다.
3. 자식이 존재하지 않는다면 반복을 종료합니다.

 

 

 

 

 

 

 

 

 

분석

삽입과 마찬가지로 시간 복잡도는 다음과 같습니다.

$$O(log\;n)$$

 

 

 

 

 

 

 

 

 

 

 

 

 

자바로 구현

https://ttl-blog.tistory.com/709

[Java] 자바로 Heap 구현하기