티스토리 뷰
큐(Queue)라는 자료구조는 선입선출(FIFO)이다. 데이터가 들어가는 위치(rear)와 나오는 위치(front)에 대한 포인터가 있다. 하지만 나중에 들어온 데이터라도 우선순위가 높다면 먼저 처리해주는게 효율적이다. 이런 자료구조를 우선순위 큐라고 한다.
큐의 경우, front에 위치해있는 데이터를 내보내고, rear에 데이터를 삽입하지만, 우선순위 큐는 구조가 다르다.
front는 모든 데이터들 중 우선순위가 가장 높은 데이터가 위치해서 우선순위에 따라 처리할 수 있도록 하고, 우선순위에 따라 처리되면 그 다음으로 우선순위가 높았던 데이터가 front로 위치하고 빈 공백을 메우기 위해 모든 데이터들이 이동한다. rear에 데이터를 삽입할 때는 front에 위치해있는 데이터와 우선순위를 비교해서 front에 있는 데이터가 우선순위가 높다면 새로운 데이터를 rear에 위치시키고, 새로운 데이터가 우선순위가 더 높다면 front로 이동시키고, front에 있던 데이터는 rear로 이동한다.
자바에서의 우선순위 큐
위 코드를 보면 알 수 있듯이 자바에서는 우선순위 큐를 Object의 배열로 구현하고 있다. 그리고 따로 지정하지 않는 한 배열의 크기는 11이다.
생성자는 아래와 같다.
아래는 Collection이나 PriorityQueue 타입으로 데이터를 받아 초기화하는 메서드이다.
아래는 우선순위 큐를 처리하는 데 관련된 메서드들이다.
3번 라인의 grow()는 우선순위 큐의 내부배열 크기를 늘려주는 메서드이다. 길이가 64보다 작을 때는 길이를 2배하다가 64와 같거나 64보다 클 때는 길이를 50%씩 늘려준다.(oldCapacity >> 1: 비트연산자)
23번 라인의 add()는 우선순위 큐에 데이터를 추가하는 메서드이다. add 내부에서 사용하는 offer() 메서드를 보면 들어갈 자리가 있는지 확인하고 자리가 없으면(if (i >= queue.length)) 우선순위 큐의 내부배열 크기를 늘려준 뒤, 우선순위를 비교하여 데이터를 넣는다. siftUp과 siftDown이 있는데 siftUp은 상향 조정, siftDown은 하향 조정이다.
poll()은 우선순위가 높은 값을 제거하는 메서드이다. 내부적으로 우선순위가 높은 값을 제거한 뒤([0]을 비운다는 의미) 데이터들을 한 칸씩 당겨온다. peek()은 위에서도 볼 수 있듯이 우선순위가 높은 값을 참조하고 싶을 때 사용할 수 있다.