개요

• 힙은 완전 이진 트리에 있는 노드 중에서 값이 가장 큰 노드나 값이 가장 작은 노드를 찾기 위해 만든 자료구조다.
• 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙, 가장 작은 노드를 찾기 위한 힙을 최소 힙이라고 한다.
• 힙은 우선순위 큐(Priority Queue)라고도 한다.

• 완전 이진 트리 : 마지막 레벨을 제외하고 모든 노드의 차수가 2인 이진 트리
  

힙의 불변성

• 힙이 되기 위한 조건이 있다.

1. 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다.
   그래서 최대 / 최소 원소는 항상 루트 노드에 존재한다.
2. 부모 노드가 자식 노드보다 항상 크거나, 작아야 한다.

성능

• 검색 및 읽기 : 최대/최소 원소에 대해서만 가능하며 O(1)이다.
• 삽입 : 완전 이진 트리이기 때문에 O(logN)이다.
• 삭제 : 최대/최소 원소에 대해서만 가능하며 O(logN)이다.

사용법

• 힙의 경우 PriorityQueue로 제공된다.
  
  

구현

• PriorityQueue의 경우 최신 라이브러리라서 프로젝트에 따라선 사용이 불가능할 수 있다. 아래는 직접 구현하는 방법이다.