Priority Queue(우선순위 큐) 정리

1. Priority Queue란 무엇인가?

 기본적으로 큐가 있고 이는 FIFO(First in First out) 구조로 되어 있다. Priority Queue는 이 FIFO 구조에 우선순위를 지정하고 우선순위가 높은 순으로 나가는 구조이다. Priority Queue는 Heap을 이용하는데 MinHeap과 MaxHeap으로 구분될 수 있다. 구조는 아래와 같다.

시간 복잡도는 O(nLogn)

Priority Queue에서 MinHeap으로 구성할 경우 자료구조에서 뽑아내면 위의 경우 10이 나오게 된다.

 

2. 그렇다면 어디에서 사용이 되는가?

 다양한 곳에서 사용이 되겠지만 예를 들면 스터디카페에 룸을 대여할 때 스터디룸 관리에 사용하는 경우가 있다.

 

3. 사용 방법

 - 선언

Queue<요소> queue = new PriorityQueue<>();
Queue<요소> queue = new PriorityQueue<>(큐길이, 우선순위);

ex) Queue<MyClass> queue = new PriorityQueue<>(5, Comparator.comparingInt(a -> a.start));
    Queue<MyClass> queue = new PriorityQueue<>();

 - PriorityQueue 클래스를 뜯어보면 생성자는 아래와 같다.

   다양한 방법으로 선언이 가능한듯...

public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
}

public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
}

public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
}

public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
}

 - 데이터 추가는 아래와 같다.

   add나 offer나 똑같다. 실행 결과는 boolean으로 반환해준다.

   데이터를 최말단 노드에 저장 후 부모노드와 비교하여 스위칭을 한다.(정렬한다는 뜻)

priorityQueue.add(Element);
priorityQueue.offer(Element);

  구조는 아래와 같다.

public boolean add(E e) {
        return offer(e);
}

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
}

 

- 데이터 반환, 삭제는 아래와 같다.

Element e = priorityQueue.poll();// 첫번째 반환
priorityQueue.remove(Element);   // 해당 Element 탐색해서 첫번째 제거 
priorityQueue.removeEq(Element); // 해당 Element 탐색해서 전부 제거
priorityQueue.clear();           // 초기화

 

- 데이터 조회

Element e = priorityQueue.peek();  // 우선순위가 가장 높은 것 반환(꺼내는게 아니고 단순조회임)
Boolean b = priorityQueue.contains(Element) // 특정 element가 존재하는지
Int checkExist = priorityQueue.indexOf(Element) // 특정 element가 존재하면 인덱스반환, 없으면 -1