[자료구조] 우선순위 큐(Priority Queue), 힙(Heap)이란?

우선순위 큐(Priority Queue)란?

큐(Queue)는 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나가는 선형 자료구조이다.
반면 우선순위 큐(Priority Queue)는 들어온 순서에 상관 없이 우선순위가 높은 데이터부터 나가는 구조이다.

우선순위 큐 표현 방법

3가지 방법이 있고 이중 JAVA의 PriorityQueue는 힙을 이용한 우선순위 큐이다.

• 배열을 이용한 우선순위 큐
• 연결리스트를 이용한 우선순위 큐
• 힙을 이용한 우선순위 큐시간복잡도 비교

  표현방법	삽입	삭제
  순서 없는 배열	O(1)	O(n)
  순서 없는 연결 리스트	O(1)	O(n)
  정렬된 배열	O(n)	O(1)
  정렬된 연결 리스트	O(n)	O(1)
  힙	O(log₂n)	O(log₂n)

  힙을 이용한 우선순위 큐가 삽입, 삭제 연산에서 모두 O(logN)의 시간복잡도를 갖기 때문에 힙이 유리하다. 따라서 일반적으로 힙(heap)을 이용하여 구현한다.

힙(Heap)이란?

• 완전 이진 트리의 일종으로 우선순위 큐(Priority Queue)를 표현하기 위해 만들어진 자료구조이다.
• 반정렬 상태로써 부모 노드와 자식 노드의 대소 관계가 성립된다.
• 최댓값 or 최솟값을 찾는 연산이 매우 빠르다.
• 이진 탐색 트리(BST)와 다르게 중복된 값이 허용된다.힙(Heap)의 종류힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있다.
  

  

최대 힙(Max Heap)

• 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리 형태이다.
• key(부모 노드) >= key(자식 노드)
• root 노드가 최댓값이고 자식 노드로 내려갈 수록 작아진다.

최소 힙(Min Heap)

• 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리 형태이다.
• key(부모 노드) <= key(자식 노드)
• root 노드가 최솟값이고 자식 노드로 내려갈 수록 커진다.

힙 정렬(Heapify)

왼쪽 자식 트리와 오른쪽 자식 트리가 모두 Heap 속성을 만족하는데 root 노드만 만족하지 않는 경우 힙의 성질을 유지하도록 재배치하는 과정을 말한다.

• root 노드와 두 자식 노드를 비교하고 두 자식 노드 중 더 큰 노드와 root 노드의 자리를 바꾼다.
• 이 작업을 반복하여 자식 노드보다 크거나 마지막 level까지 갔을 때 중단한다.

힙(Heap)의 삽입/삭제 연산

특정 값을 삽입하거나 삭제했을 때 힙(heap) 성질을 유지하기 위해 재배치하는 과정이 있다.
이때 삭제 연산에서는 Heapify 연산이 일어난다.

삽입

1. 마지막 위치에 삽입
2. 정상적인 힙(Heap)이 될 때까지 부모 노드와 자식 노드를 비교하여 자식 노드가 부모 노드보다 크다면 부모 노드와 위치 교환한다.
   

   

삭제

1. root 노드를 삭제한 후 마지막 노드를 root에 가져온다.
2. Heapify 연산을 실행하며 정상적인 힙(Heap)이 될 때까지 반복한다.

힙(Heap) in JAVA

• JAVA에서 힙은 우선순위 큐(PriorityQueue) 자료구조를 이용한다.
• PriorityQueue는 기본적으로 Min-Heap을 제공하고 Collections 을 사용해서 최대 힙으로 변경 가능하다.
  • 최소 힙
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
  • 최대 힙
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue 메서드

삽입

• pq.add(삽입할 value);
  반환 값: 삽입 성공 시 true 반환 / 삽입 실패 시 Exception 발생
• pq.offer(삽입할 value);
  반환 값: 삽입 성공 시 true 반환 / 삽입 실패 시 false 반환

삭제

• pq.remove();
  반환 값: 삭제 성공 시 우선순위가 높은 값 삭제 후 반환 / 공백 큐이면 Exception("NoSuchElementException") 발생
• pq.remove(삭제할 value);
  반환 값: 큐에 해당 값이 존재한다면 삭제 후 true 반환 / 큐에 해당 값이 존재하지 않으면 false 반환
• pq.poll();
  반환 값: 삭제 성공 시 우선순위가 높은 값 삭제 후 반환 / 공백 큐라면 null 반환

우선순위가 높은 값 반환(삭제하지 않고 반환만)

• pq.element();
  반환 값: 우선순위가 높은 값 반환 / 공백 큐이면 Exception("NoSuchElementException") 발생
• pq.peek();
  반환 값: 우선순위가 높은 값 반환 / 공백 큐이면 null 반환

큐 초기화(공백 큐 만들기)

• pq.clear();
  반환 값 없음

큐 크기

• pq.size();
  큐 크기 반환

큐에 해당 원소가 존재하는가?

• pq.contains(찾을 value);
  반환 값: 해당 값이 존재하면 true 반환 / 존재하지 않다면 false 반환

큐에 값이 존재하는가?

• pq.isEmpty()
  반환 값: 큐가 비어 있다면 true 반환 / 비어 있지 않다면 false 반환

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // 최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 최대 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 추가 (삽입)
        minHeap.add(10);
        minHeap.offer(30);
        minHeap.add(20);
        minHeap.offer(5);

        // 요소 제거 (삭제) - 최소값이 먼저 제거됨
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // poll()은 제거된 요소를 반환
        }
    }
}