Priority Queue란?

Queue는 FIFO 구조이지만, Priority Queue는 우선순위를 결정하고 그

우선 순위에 따라 Dequeue를 진행하는 자료 구조 (BIFO, Best in First Out )

내부적으로는 Heap으로 구현되어, 이진트리 구조

우선 순위(Key)는 Unique할 필요가 없고, 변경될 수 있음.

우선 순위를 필요로 할 때 사용

Method

• add(E e)

• offer(E e)

: PQ에 값 추가, return True(추가 됐을때)
   넣을 수 없는 상황이면 add는 exception, offer는 false retrun

• peek()

: return 삭제하지 않고 Min or Max 값
    

• remove(Object o)
• poll()
• clear()

: 해당 객체 삭제, 우선 순위 값 삭제, 전체 삭제

• contains(Object o)

: return True, 값이 존재하면

• size()

: return int

• isEmpty()

: return True, False(boolean)

---

• removeAll(Collections c)
• removeIf(Predicate<? super E> filter)
• toArray() (Obejct때)
• toArray(T[] a)

---

기본 동작

추가 작업이 없으면 Min heap 으로 동작

PQ 생성시 생성자로 Comparator, Comparable를 정의해주면 Max Heap으로 동작 (Collections.reverseOrder() 사용)

Class 등을 element로 사용할 경우엔, Comparable을 이용해서 CompareTo를 Override 가능

Comparator.comparing((Student student) -> student.getAge())로 할 수 도 있음

public void test_student_age() {
        int capacity = 4;
        PriorityQueue<Student> studentAgeHeap = new PriorityQueue<>(capacity, Comparator.comparing((Student student) -> student.getAge()));

        studentAgeHeap.add(new Student("Frank", 23));
        studentAgeHeap.add(new Student("Angela", 10));
        studentAgeHeap.add(new Student("David", 30));
        studentAgeHeap.add(new Student("Joe", 15));

        assertThat(studentAgeHeap.poll().getName()).isEqualTo("Angela");
        assertThat(studentAgeHeap.poll().getName()).isEqualTo("Joe");

}

시간 복잡도

boolean add(E element)

: O(N log N) ,	우선순위에 따라서 큐에 삽입한다.

public peek()

: O(1), 큐의 first 아이템을 제거하지 않고 확인할 수 있다

public poll()

: O(1), 큐의 first 아티엠을 제거하고 데이터를 반환한다