PriorityQueue 살펴보기

공부하게 된 계기

PriorityQueue를 꽤나 자주 사용하지만, 우선순위로 정렬하여 결과를 보여준다라고만 생각하고 있었습니다. 

우선순위로 정렬을 하니, 전형적인 큐의 특성만 생각하여 넣을때마다 선형적으로 정렬되어 들어있을거라고 막연히 생각했었습니다. 최근에 알고리즘 문제를 풀며 PriorityQueue를 쓰게 되었는 데, 디버깅 과정에서 예상과는 다르게 정렬되어 있지 않은 것을 발견하고 왜 그런가를 확인해보게 되었습니다.

 

public class Person {
	private int age;
	private String name;

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

	public int getAge() {
		return age;
	}

	public String getName() {
		return name;
	}
}

class PersonTest {
	@Test
	@DisplayName("PriorityQueue 순서 확인")
	void priority_queue() {
        // Comparator 를 구현하여 생성자로 넘겨줌
		PriorityQueue<Person> people = new PriorityQueue<>(Comparator.comparing(Person::getAge));
		people.offer(new Person(15, "aaa"));
		people.offer(new Person(20, "aaa"));
		people.offer(new Person(11, "aaa"));
		people.offer(new Person(30, "aaa"));
		people.offer(new Person(33, "aaa"));
		people.offer(new Person(3, "aaa"));
		people.offer(new Person(13, "aaa"));
		people.offer(new Person(14, "aaa"));
		people.offer(new Person(15, "aaa"));

		while (!people.isEmpty()) {
			System.out.println(people);
			System.out.println(people.poll());
		}
	}
 }

나이순으로 정렬한 코드입니다. 위의 로그와 같이 선형적이지 않은 모습으로 들어가 있는 것을 확인할 수 있습니다.

이러한 특성은 PriorityQueue 가 자료구조인 heap 을 생성하며 정렬되기 때문입니다.(물리적으로는 Object 배열입니다)

heap 은 정렬상태를 느슨하게 유지하기 때문에, 삽입(O(logN)) 과 삭제(O(logN)) 가 빠르게 실행됩니다.

 

PriorityQueue 의 삭제 동작

루트노드가 poll 로 인해 삭제

루트노드가 poll 로 인해 삭제

특성

PriorityQueue 는 Comparable 을 구현한 클래스이거나, 생성시에 Comparator 구현체를 전달해야 합니다. 

위의 예제에서는 Comparator 구현체를 전달하였습니다. Comparable 을 구현한 클래스이지만 Comparator 구현체를 생성자로 넘겼을 경우에는 Comparator 구현체의 정렬을 우선순위로 합니다.

Comparable 을 구현하지 않았고, Comparator 구현체가 생성자를 통해 전달되지 않았다면, ClassCastException 이 발생합니다. 이는 생성자에 Comparator 가 전달되지 않으면 siftUpComparable 메서드에서 Comparable 로 캐스팅하기 때문입니다.

PriorityQueue 에 원소를 추가시 index가 0이아니면(첫번째 원소가 아니면) siftUp 을 호출

생성자로 Comparator를 전달받지 않았으면 siftUpUsingComparable 실행

캐스팅을 시도

offer(삽입), poll(삭제) 메서드를 실행 시 heap 구조를 유지합니다. siftUpComparator 메서드와 siftUpUsingComparable 메서드의 차이는 compare 를 뭘로 하느냐의 차이만 있습니다. parent 노드의 인덱스를 구하는 구현이 꽤나 인상적입니다. 시프트 연산을 통해 부모노드를 구합니다.

 

PriorityBlockingQueue

PriorityQueue 는 thread safe 하지 않기 때문에, 멀티쓰레드 환경에서 여러 쓰레드가 해당 자료구조에 접근해야 할 경우에는 PriorityBlockingQueue 를 사용해야 합니다.

ReentrantLock 을 통해 thread safe 한 구현을 하고 있습니다.

 

정리

이상으로 PriorityQueue 에 대해 알아보았습니다. 해당 클래스의 구현을 확인하며, heap 자료구조에 대해서도 다시 한번 살펴볼 수 있었고, heap 을 구현한 Java api 를 참고할 수 있었어서 좋았던 거 같습니다. 라이브러리의 세부 구현을 모두 확인할 필요는 없지만(할 수도 없고) 이런 계기로 인해 좀 더 깊이있게 공부해보는 것도 좋은 경험이라고 생각합니다.

 

https://github.com/pch8388/study-java-base/blob/master/src/test/java/me/study/base/compare/CompareTest.java