📖 우선순위 큐

---

💬 힙(Heap)

• 완전 이진 트리에 있는 노드 중 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조

◾ 최대 힙(Max Heap)

• 키값이 가장 큰 노드 찾기 위한 완전 이진 트리
• 부모 노드 키값 > 자식 노드 키값
• 루트 노드 : 키값이 가장 큰 노드

◾ 최소 힙(Min Heap)

• 키값이 가장 작은 노드 찾기 위한 완전 이진 트리
• 부모 노드 키값 < 자식 노드 키값
• 루트 노드 : 키값이 가장 작은 노드

삽입 연산 과정

1. 비어있는 자리로 임시 삽입
2. 부모 노드와 위치 변경하면서 위치 변경
3. 자리 확정되면 끝

삭제 연산 과정

• 루트 노드만 삭제 가능

1. 루트 노드 삭제
2. 마지막 노드 루트 노드 위치로 이동
3. 자식 노드와 비교하며 위치 변경
4. 자리 확정되면 끝

💬 우선순위 큐 특징

1. 높은 우선순위의 원소 먼저 출력 (원소는 비교 가능한 기준이 있어야 함)
2. 내부 요소는 heap으로 구성되있는 완전 이진트리 구조
3. 시간 복잡도: 삽입 O(logN), 삭제O(logN)
4. 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산에 사용

💬 우선순위 큐 메소드

• Priority Queue 선언
  • PriorityQueue<Element> pq = new PriorityQueue<>(); : 오름차순
  • PriorityQueue<Element> pq = new PriorityQueue<>(Collections.reverseOrder()); : 내림차순

메소드	설명
boolean add(E e)	전달된 Element 삽입
E element()	Element를 반환하지만 제거는 안됨
boolean offer(E e)	전달된 Element 삽입
E peek()	가장 마지막 원소 확인 (없으면 null 반환)
E poll()	가장 앞 원소 반환 후 제거 (없으면 null 반환)
boolean remove(Object o)	전달된 원소 제거
Comparator< ? super E > comparator()	요소 정렬에 사용되는 비교자 반환 또는 정렬될 경우 null 반환
boolean contains(Object o)	전달된 요소가 있는 경우 true 반환
int size()	이 큐의 요소 수 반환
Object[] toArray()	모든 요소 포함한 배열 반환
Iterator< E > iterator()	이 큐 요소에 대한 반복자 반환

• 이 외에도 Collection에서 제공하는 메소드 사용 가능
  addAll, clear, contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, size, toString 등