우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐

• 우선순위 큐는 큐와 비슷하지만 먼저 들어온 데이터가 먼저 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 나간다. 
  • 큐: 먼저 들어온 데이터가 먼저 나간다. (FIFO)
  • 우선순위 큐: 우선순위가 높은 데이터가 먼저 나간다.
• 우선순위 큐는 추상적인 개념이고, 주로 힙을 통해 구현된다.

힙

• 힙은 우선순위 큐의 구현 방식 중 하나로 주로 이진 트리 기반으로 구현된다. (이진 트리: 자녀가 최대 두 개인 트리)
• 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 이진 트리이다.

• 최소 힙(Min Heap): 부모 노드의 키가 자식 노드의 키보다 작거나 같은 이진 트리이다.

• 힙의 주요 동작은 다음과 같다.
  • insert: 힙에 데이터를 넣어주는데 이때 데이터의 키 값도 함께 넣어준다.
  • delete: max heap이면 키 값이 가장 큰 데이터가 가장 높은 우선순위이므로 키 값이 가장 큰 데이터를 제거한다. 반면 min heap이면 키 값이 가장 작은 데이터가 가장 높은 우선순위이므로 키 값이 가장 작은 데이터를 제거한다.
  • peek: delete와 유사하나 실제 힙에서 데이터를 제거하지는 않는다.

• 우선순위 큐와 힙의 관계: 우선순위 큐는 ADT로 실제 구현은 설명하지 않고 어떻게 동작하는지 그 개념만 설명한다. 반면 힙은 자료구조로 구현까지 설명한다. 즉 힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다. 

자바에서의 우선순위 큐 구현

• 자바는 Priority Queue 클래스를 제공한다.
• Priority Queue를 사용하기 위해선 큐에 저장할 객체는 반드시 Comparable 인터페이스를 구현하며 compareTo 메소드를 오버라이드해야 하며 우선순위 조건을 지정해주어야 한다.

우선순위 큐와 힙의 사용 사례

• 프로세스 스케줄링: 우선순위에 따라 스케줄링되어야 한다면 ready queue에 우선순위 큐를 사용할 수 있다.
• 힙 정렬: 정렬해야 하는 n개의 데이터를 힙에 넣은 뒤 차례대로 delete하면 우선순위가 높은 데이터가 먼저 나와 정렬된다.