Queue : FIFO, 우선순위 큐랑 다름

Priority Queue : 새치기가 가능한 큐 ⇒ heap 구조 (Tree 구조 중 CBT)

cf) 트리구조

• Full Binary Tree

  

  ⇒ 최대 두 개의 자식 가질 수 있다.

  ⇒ 순서대로 안 차도 됨

• Complete Binary Tree

⇒ 무조건 왼쪽부터 채워짐

• Perfect Binary Tree

⇒ 모든 층에 대한 트리가 꽉 차 있는 것을 말함.

⇒ 큐랑 같은 명령어 사용.

// Priority Queue
// -> 우선순위 큐는 정렬된 형태를 가지지 않습니다. **(정렬 X)**
// -> 우선순위가 가장 높은 요소가 가장 먼저 빠져나올 수 있게 하도록 균형을 유지
// -> 가장 먼저 빠져나올 (우선순위가 가장 높은 요소) 외에는 전혀 관심이 없는 구조
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(2);
pq.add(3);
pq.add(4);
int de = 1;

// 삭제 (우선순위 큐에서 가장 우선순위가 높은 것을 빼온다)
pq.remove()

<aside> ✅ Priority Queue가 구조를 유지하는 방법

• heapify → 내 부모(또는 child랑) 비교해서 나보다 우선순위가 낮으면 왕좌를 뺏어옵니다. (swap)

Java에서 default priority queue = MIN heap ⇒ (int 기준으로) 가장 작은 값이 먼저 나오게 하는 구조 ⇒ 가장 우선순위가 높은 것을 항상 root 위치에 두는 것이 목표

</aside>

• Priority Queue 시간복잡도

  • 삽입 : O(log(N))

  • 삭제 : O(log(N))

    ⇒ 재밸런싱이 굉장히 간단. 트리맵의 경우도 log(N)이지만 훨씬 빠름

  • peek : O(1)

static class Node implements Comarable <Node> {
		int y;
		int x;
		Node(int y, int x) {
				this.y = y;
				this.x = x;
		}
		@Override
		public int compareTo(Node o) {
				if (y < o.y) return -1;
				if (y > o.y) return 1;
				if (x < o.x) return -1;
				if (x < o.x) return 1;
				return 0;
		}
}

PriorityQueue<Node> npq = new PriorityQueue<>();
npq.add(new Node(0, 0));
npq.add(new Node(100, 0));
npq.add(new Node(0, 100));
npq.add(new Node(3, 7));
npq.add(new Node(3, 8));
while(!npq.isEmpty()) {
		Node now = npq.remove();
		System.out.println(now.y + " " + now.x);
}

<aside> ✅ 키워드 : 우선 순위 ** Time flow라는 유형과 같이 나오는 경우 많음. —> Priority Queue는 일반적으로 이런 상황에서 일단 쑤셔 넣고 나올 때 확인하는 방식 —> 보통 DAT와 같이 쓰는 경우가 많음. ——> 시간이 지나가는 것. ** Graph와도 굉장히 많이 나오는 형태 항상 둘 다 쓸 수 있어도 PriorityQueue가 TreeMap보다 성능은 높음 ——> 웬만해서는 TreeMap이 구현은 쉬움 ——> TreeMap으로 먼저 구현해봄 → 시간 될 것 같다? 제출 → 최적화 하고 싶다? PriorityQueue로 변환

                   **TreeMap**                 vs                **Priority Queue**

시간 log(N) log(N) <—— 훨씬 빠른 logN 중복 X O 조건부 탐색 내부 탐색 절대 안함 class 사용 시 주의 문자열 key 주의 빈번한 삭제가 존재할 시 주의 요소가 너무 많이 들어갈 수 있다면 주의

</aside>