힙(Heap)

학습 목표

힙 자료구조의 이해

최소 힙과 최대 힙의 삽입, 삭제 과정의 이해와 구현

 

 

힙(Heap) : 최소 값 또는 최대 값을 빠르게 찾아내는데 유용한 자료구조입니다.

1. Tree가 Complete or Nearly Complete.(중복 값 허용, 반 정렬 상태)

2. 최대 힙(Max Heap) : 부모 노드의 키 값이 자식의 키 값보다 크거나 같습니다.

    최소 힙(Min Heap) : 부모 노드의 키 값이 자식의 키 값보다 작거나 같습니다.

 

 

최소 힙(Min Heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 형태입니다.

 

Operation of Min Heap

 

최소 힙 - 삽입(Insertion)

1. 트리의 가장 끝 위치에 데이터 삽입합니다.

2. 부모 노드와 키 값을 비교한 후 작을 경우 부모 노드의 자리와 교체합니다.(반복)

 

최소 힙 - 삭제(Delete)

1. 최상위 노드 반환 및 삭제합니다.

2. 가장 마지막 위치의 노드를 최상위 노드로 위치 시킵니다.

3. 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리를 교체 합니다.(반복)

 

최대 힙(Max Heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 형태입니다.

 

Operation of Max Heap

 

최대 힙 - 삽입(Insertion)

1. 트리의 가장 끝 위치에 데이터 삽입합니다.

2. 부모 노드와 키 값을 비교한 후 클 경우 부모 노드의 자리와 교체합니다.(반복)

Before reheap up

After reheap up

최대 힙 - 삭제(Delete)

1. 최상위 노드 반환 및 삭제합니다.

2. 가장 마지막 위치의 노드를 최상위 노드로 위치 시킵니다.

3. 자식 노드 중 큰 값과 비교 후 부모 노드가 더 작으면 자리를 교체 합니다.(반복)

Before Delete

After Delete

 

 

 

 

Heap 메소드

heap은 java내장 메소드가 존재하지 않습니다.

 

 

시간 복잡도(Time Complexity)

삽입(Insertion) = O(log n)

삭제(Deletion) = O(log n)

최소/최대 값 검색(Min/MaxSearch) = O(1)

 

 

 

 

 

 

References

- Chapter 9. Heaps, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.