PriorityQueue<E> 사용하기

최근 코딩 테스트 문제 중 Heap 관련 문제를 풀어보다가 로직은 맞지만 시간초과로 인해 계속 통과를 

하지 못하는 상황이 발생했다..

단순히 문제에서 주어진 변수타입으로만 문제를 풀어보려했다. 그리고 그것이 더욱 제한된 상황에서의 문제 해결이라

더 난이도가 높은 수준으로 처리하는 것이라고 생각했다.

그리고 나는 각 언어의 장점(언어마다 제공하는 기본 함수)을 살려서 작업을 처리하는것도 좋지만 어느 언어나 있고 가장 기본적인 함수와 문법을 이용하여 푸는것이 먼저 중요하고 한 언어에 종속 되는것보다 나은것이라고 생각했다.

그리고나서 그 언어에 더 심도있게 알아가며 편리하게 사용가능한 함수들을 알아가고 사용하는것이라고.

하지만 이번 문제는 그렇지 않았다. 아무리 여러 방법으로 처리해도 되지가 않았다.

결국 PriPriorityQueue<E>를 쓰니 너무도 황당하게도 쉽게 풀리는 문제였다.

 

어쨋든,

 

PriorityQueue<E> 란?

번역 그대로 우선순위 큐이다. 하지만 우선순위라는 말답게 일반 Queue와는 다른다.

일반적인 Queue는 선입선출(FIFO)이 기본이기 때문에 넣어진 데이터순 그대로 정렬되어있다.

하지만 PriorityQueue<E>는 우선순위에 따라 원소들을 자동 정렬해준다.

만약 다음과 같이 제네릭을 Integer로 설정하고 생성자에 아무런 파라미터를 설정하지 않으면

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

add나 offer를 사용하여 원소들을 넣을때마다 원소들을 자동으로 오름차순으로 정렬하여 준다.

 

Priority Queue 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.
   우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다.
4. 우선순위를 중요시해야 하는 상황에서 주로 쓰인다.

여기서 중요한 점은 힙으로 구성되어 있어 이진트리 구조라는것이다.

아래의 예를 보자.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

priorityQueue.add(40);
priorityQueue.add(70);
priorityQueue.add(50);
priorityQueue.add(100);

        
// priorityQueue의 원소 순서를 확인해보면
// 40, 70, 50, 100 순으로 정렬되어 있다

위에서 자동정렬 해준다고 말했으면서 실제로 원소들은 40, 70, 50, 100 순으로 저장되어 있다.

왜일까?

위에 강조한 이진트리 구조라서 그렇다.

velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

이진트리 구조는 위에 링크에 아주 잘 설명되어있다.

 

즉, 이진트리 구조에서의 우선순위는 결국 부모와 자식간의 우선순위를 따질뿐이다.

그래서 자식레벨의 값이 부모레벨의 형제의 값보다 큰 경우도 발생할 수 있는것이다.

 

그리고 참고로 <> 안에 들어가는 제네릭은 primitive 형의 데이터타입은 들어갈 수가 없다. (int, float.. 이런거 안된다)

하지만 자바에는 int도 Integer라는 wrapper 클래스가 있고 다른 데이터형들도 마찬가지다.

이것들을 활용하면 된다.

 

 

값을 넣는 주요한 멤버 메소드로는

//add ()는 Queue에 현재 사용 가능한 공간이 없으면 IllegalStateException
priorityQueueLowest.add(100);

//용량 제한으로 인해 요소를 삽입 할 수없는 경우 offer () 메서드는 false를 반환
priorityQueueLowest.offer(30); 

add는 공간이 없으면 예외를 발생시킨다는데, priorityQueue는 기본적으로 데이터를 넣을때마다 자동으로 크기를 늘리고 넣어준다고 알고 있었는데, 어딘가는 또 저렇게 사용공간이 없을시 예외를 발생시킨다고 한다.

정확히는 모르겠으나 차후 알아가도록하자.

그리고 add 쓰더라도 내부적으로는 offer가 동작한다고 한다.

 

 

 

값을 꺼내는 주요한 멤버 메소드로는

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();     

아마도 이것들을 많이 쓰게 될것같다. (예외발생은 좋아하지 않기때문에)

priorityQueueLowest.poll();

priorityQueueLowest.pe

priorityQueueLowest.clear();

 

 

 

참조 : 

velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

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

siyoon210.tistory.com/117