우선순위 큐(Priority Queue)와 힙(Heap) 자료구조

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용

• 대표적인 우선순위 구현 방법 : 리스트, 힙(heap) 자료구조
• → 힙 자료구조를 사용할 때 삽입&삭제 모두 O(logN)

---

힙(Heap) 자료구조

• 완전 이진트리 자료구조의 일종
• 항상 루트 노드를 제거한다.
• 최소 힙 (min heap)
  • 루트 노드가 가장 작은 값을 가진다
  • 값이 작은 데이터가 우선적으로 제거된다
  • 최소 힙 구성 함수 : Min-Heapify()
• 최대 힙 (max heap)
  • 루트 노드가 가장 큰 값을 가진다
  • 값이 큰 데이터가 우선적으로 제거된다

🅰️ Heap
더미, 쌓다, 수많은, 엄청난

---

완전 이진 트리 (Complete Binary Tree)

루트노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미

---

JAVA의 우선순위 큐

import java.util.PriorityQueue;
import java.util.Collections;

// 최소힙 우선순위 큐
PriorityQueue<Integer> pQmin = new ProiroityQueue<>();

// 최대힙 우선순위 큐
PriorityQueue<Integer> pQmax = new PriorityQueue<>(Collections.reverseOrder());

// add
pQmin.add(1);
pQmin.add(10);
pQmin.add(100);

pQmax.add(1);
pQmax.add(10);
pQmax.add(100);

// remove
pQmin.poll(); // 첫번째 값 반환하고 제거. 비어있다면 null 반환
pQmin.remove(); // 첫번째 값 제거. 비어있다면 예외 발생
pQmin.peek(); // 첫번째 값 반환만 하고 제거X. 큐 비어있으면 null 반환
pQmin.element(); //첫번째 값 반환만 하고 제거X. 큐 비어있으면 예외 발생
pQmin.clear(); // 초기화

 

커스텀 클래스로 우선순위 큐 사용 시

Comparable 인터페이스 구현하여 compareTo를 우선순위에 맞게 override 해줘야 한다.

class Member implements Comparable<Member {
	String name;
	int age;

	Member(String name, int age) {
		this.name = name;
		this.age = age;
	}

	@Override
	public int compareTo(Member o){
		return this.age - o.age; // 나이 오름차순 정렬
	}
}

public static void main(String[] args){
	PriorityQueue<Member> pQ = new PriorityQueue<>();
	pQ.add(new Member("김방실", 5));
	pQ.add(new Member("김몽실", 4));
	pQ.add(new Member("김보리", 2));
	pQ.add(new Member("문쭈니", 9));

	while(!pQ.isEmpty()){
		Member member = pQ.poll();
		System.out.println("["+member.name+" "+member.age+"]");
	}
}

// 실행결과
김보리 2
김몽실 4
김방실 5
문쭈니 9

---

참고자료

자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약

[Java] Priority Queue(우선 순위 큐)