[ 자료구조 ] 힙 (Heap)

Heap 이란?

우선순위큐를 위해 고안된 완전이진트리 형태의 자료구조, 여러값 중 최대/최소값을 빠르게 찾아내도록 만들어진 자료구조.

▶ 완전 이진트리 : 노드가 왼쪽부터 채워지는 형태

 

 

 

 

Heap의 종류

1. • 최소 힙 (min heap) : 부모노드 <= 자식노드
   • 최대 힙 (max heap) : 부모노드 >= 자식노드

 

 

 

데이터 삽입

1. 최소 힙에 저장
    - 삽입되는 값을 상위 부모노드와 비교하여 더 작을 경우 위로 swap 

 

2. 최대힙에 저장
    - 삽입되는 값을 상위 부모노드와 비교하여 더 클 경우 위로 swap 

 

 

 

데이터 삭제

최소/최대힙의 가장 최상위 노드가 결국 최소값, 최대값이 되며, 힙 자료구조는 최소/최대값을 알아내는것이 목표임

따라서, 데이터를 삭제하면 최소/최대값이 삭제된다.

 

• 최대힙 삭제 예시
  
  
  

15의 자식인 10,8중 8의 우선순위가 높은 8과 비교를 진행한다.

 

 

 

시간 복잡도 O(logN)

최악의 상황은 가장 root노드와 비교까지 할 경우이다. 이 경우는 모든 트리의 경우를 다 비교하는것이다.

 

 

 

 

참고 사이트

https://currygamedev.tistory.com/20

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기

[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)