[Java] Priority Queue 들여다 보기

서론

pq는 문제 풀면서 자주 쓰는 친구 중 하나다.

간단히 아는 바로는

heap 구조를 쓰고

heap에는 max heap, min heap이 있지만

자바에서는 Comparator를 파라미터로 넘겨줘서

우선순위를 자유롭게 커스텀 하는게 가능하다 정도?

 

이 정도만 알아도 쓰는데는 지장 없지만 클래스 내부가 생각보다 복잡하길래 한번 들여다보려고 한다.

총 라인수가 주석포함 900줄 정도.. 다는 못보고 내 눈에 띄는 것만 간단히 봐보았다.

 

시작!

여까지 보면 우선 AbstractQueue를 상속받는다 이름 그대로 큐에 필요한 함수들이 정의된 추상클래스이다.

그리고 직렬화가 가능하다. 그래서 serialVersionUID도 가지고 있다.

 

다음으로 DEFAULT_INITIAL_CAPACITY는 시작 PQ의 크기인데 왜 애매하게 11일까..

그런데 큐는 LinkedList로 만들어지는데 시작크기라는 개념이 왜 필요하지...?

 

Queue가 Array

그렇다 pq에서 큐는 LinkedList로 구현되어 있지 않다.

heap 구조 자체가 완전이진트리이니 인덱스를 주는게 가능하고

offer나 poll을 할때도 값 전체가 뒤로 밀리거나 당겨지지 않고

인덱스 간 값 이동만(logN번) 일어나니 확실히 array로 구현하는게 효율적으로 보인다.

(생각해보면 pq는 FIFO가 아닌데 왜 큐라고 불리는지 흠...)

 

transient

그런데 transient는 처음 보는데 무엇일까?

transient는 Serialize하는 과정에 제외하고 싶은 경우 선언하는 키워드입니다. 라고 한다.

데이터를 전송하고 싶지 않을때 사용한다고 한다. 저거를 선언하면 null로 보내진다고.. 왜지..?

직렬화를 하는건 데이터를 보내고 싶은거고 제일 중요한 데이터는 실제 들어간 값일텐데 왜지..?

 

왜 transient에요?

https://newbedev.com/why-does-arraylist-use-transient-storage

ArrayList도 pq랑 비슷한 형태라 관련해서 찾아봤다.

간단히 요약하면 원래 있던 직렬화를 쓰면 여러모로 별로라

custom readObject랑 writeObject를 이용해 직렬화를 제공하여 공간 절약을 한다고 한다.

 

아무래도 ArrayList나 pq나 내부적으로 array를 두고 원소 갯수가 많아지면

그거에 맞춰 미리 크기를 키워 놓는 작업을 하니 null로 채워져 있는 부분도 직렬화해서

데이터를 넘기는 것을 방지하기 위해 따로 함수를 만들었나 보다.

 

실제로 구현부를 보면 size까지만 데이터를 write하는 것을 볼 수 있다.

 

----------------------------------------------------------