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

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

구현방법

1. 리스트를 이용하여 구현
   삽입시간 : O(1)
   삭제시간 : O(N)
2. 힙 자료구조를 이용하여 구현
   삽입시간 : O(logN)
   삭제시간 : O(logN)
3. 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙정렬) -> O(NlogN)

힙의 특징

• 힙은 완전 이진 트리(Complete Binary Tree) 자료구조의 일종
• 힙에서 항상 루트 노드를 제거
• 최소 힙 : 루트 노드가 가장 작은 값
• 최대 힙 : 루트 노드가 가장 큰 값
• 힙의 원소를 제거할때
  루트 노드 값을 제거하고, 루트 노드값에 가장 밑에 있는 노드 값(최대값)을 넣고 다시 정렬함

코드

//int형 priorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 
 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
 
//삽입
priorityQueue.offer(1);
//삭제
priorityQueue.poll();
//읽기
priorityQueue.peek();