[자바] Heap 사용 방법 및 예제: java.util.PriorityQueue

Heap 이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

* 완전 이진 트리

 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

인덱스

• 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
• 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

 

JAVA Heap: PriorityQueue

PriorityQueue (Java Platform SE 8 )

import java.util.PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

 

메소드

add(), clear(), comparator(), contains(Object o), iterator(), offer(E e), peek(), poll(), remove(Obeject o), size(), spliterator(), toArray(), toArray(T[] a)

 

사용 방법 및 예제

PriorityQueue 선언

import java.util.PriorityQueue;

//오름차순(default) PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//내림차순 PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

• 조건 없이 선언 시에 디폴드 값으로 오름차순 생성
• Collections.reverseOrder()를 추가해서 선언할 경우 내림차순 생성

 

PriorityQueue 삽입

• add(E e)
• offer(E e)

 

PriorityQueue 삭제

• clear() : 모든 요소 삭제
• poll() : 헤드 요소 조회 및 삭제, 큐가 비어있을 경우 null 반환

 

PriorityQueue 조회

• peek() : 헤드 요소 반환, 큐가 비어있을 경우 null 반환