[Java] PriorityQueue(우선 순위 큐) 분석하고, 따라 구현해보기

 

---

우선 순위 큐 (Priority Queue)

최소 혹은 최대값을 효율적으로 찾을 수 있는 자료 구조

 

- 시간 복잡도 :  O( log₂N) 

- 힙(완전 이진 트리) 자료 구조 기반 구현

 

 

- (사전에 정렬할 필요 없이) 데이터 삽입/삭제 시 우선 순위에 따라 빠르게 접근/삭제 가능하다

① 최소 힙 : 부모 노드 ≤ 자식 노드 

② 최대 힙 : 부모 노드 ≥ 자식 노드

 

참고. 부모-자식 인덱스 구하는 공식

루트가 0번 인덱스부터인 경우

① 부모 노드 = (현재 노드 - 1) / 2

② 왼쪽 자식 노드 = (부모 노드 * 2) + 1

③ 오른쪽 자식 노드 = 왼쪽 노드 + 1

 

 

 

구현해보기

java.util.PriorityQueue 에서 간단하게 필요한 부분만 추출하였다

public class MyPriorityQueue<E> {
    private static final int DEFAULT_INITIAL_CAPACITY = 11; // 초기 용량
    
    Object[] queue;

    int size;

    private final Comparator<? super E> comparator;

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

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

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

    public MyPriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if(initialCapacity < 1)
            throw new IllegalArgumentException();

        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
    
    // 기타 메소드
}

 

기본 생성자 사용할 경우 초기 용량 11로 생성이 되고, comparator는 null 처리 된다

 

여기서 Comparator<? super E> comparator를 지정하지 않았는데 어떻게 우선 순위가 정해지는지 궁금하였다

찾아본 결과 데이터 삽입/삭제시 아래와 같이 comparator가 null 인 경우 수행하는 메소드가 분리되어 있었다

 

신규 추가하는 데이터에 해당하는 T x를 Comparable<? super E>로 캐스팅하여 사용하는데,

Comparable 구현된 Wrapper Class에  compareTo(..) 를 사용하여 조건식을 수행하였다

 

예로 T가 Integer인 경우 Integer 클래스에 구현되어 있는 compareTo(..) 를 사용하였다

 

 

참고. Integer 클래스에 구현된 Comparable 사용시 기본 오름차순, 최소힙으로 동작한다

 

---

add(E e), offer(E e) - 데이터 추가 

우선 순위 큐에서는 데이터 추가할 경우 아래와 같은 절차를 수행한다

① 마지막 인덱스에 데이터 추가한다

② 상향식으로 부모 노드 ~ 최대 root 노드까지 대소관계 비교하여 heapify 수행한다

 

 

 

구현해 볼 메소드는 아래와 같다

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

public boolean offer(E e) {
    // ..
}

// k : size , x : add Element
private void siftUp(int k, E x) { 
    // ..
}

// Comparator가 없는 경우
private static <T> void siftUpComparable(int k, T x, Object[] es) {
    // ..
}

// Comparator가 주어지는 경우
private static <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> comparator) {
    // ..
}

 

 

offer(E e) 구현

배열 크기를 늘리는 부분(주석) 제외하면 어려운 건 없었다

public boolean offer(E e) {
    if(e == null)
        throw new NullPointerException();

    final int i = size;

    // i >= queue.length 인 경우 grow(i + 1) 생략

    siftUp(i, e); // i : 마지막 인덱스, e : 신규 데이터
    this.size += 1;
    return true;
}

 

 

siftUp(..) 구현

comparator 존재여부에 따라 조건 분기 처리해준다

private void siftUp(int k, E x) { // k : size , x : new Element
    if(comparator != null)
        siftUpUsingComparator(k, x, this.queue, this.comparator);
    else
        siftUpComparable(k, x, this.queue);
}

 

 

siftUpComparable(..) 구현 

- 조건을 만족할 때까지 우선 순위 비교하여 swap을 수행한다

- 그리고 최종 k 위치에 신규 데이터 x 값을 넣는다

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while(k > 0) {
        int parent = (k - 1) >>> 1;
        Object c = es[parent];

        if(key.compareTo((T) c) >= 0)
            break;

        es[k] = c;
        k = parent;
    } 
    es[k] = x; // 최종 k 위치에 x를 넣는다
}

 

① int parent = (k - 1) >>> 1

- 최초 k는 마지막 인덱스를 가르킨다

- k 인덱스의 부모 노드 인덱스를 구할 때, -1을 해준 후 절반으로 나눈다 (루트가 0번부터 시작하기 때문에 -1을 해준다)

- shift operator(>>>)가 낯설지만 오른쪽으로 1bit 이동시키는 행위는 값을 1/2 한 것과 같다

- 예로 k = 2일때 부모 노드는 (k - 1) / 2 = 0 이다

 

② if(key.compareTo((T) c) >= 0)

- 앞서 살펴봤듯이 추가되는 값 T x의 T 클래스에 구현되어 있는 Comparable 메소드를 사용하여 비교를 수행한다

- 예로 T가 Integer인 경우 Integer 클래스에 구현되어 있는 compareTo(..) 사용

 

 

siftUpUsingComparable(..) 구현 

위에 siftUpComprable(..) 동일한 로직에서 casting 없이 주입받은 comparator를 사용하기만 하면 되었다

private static <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> comparator) {
    while(k > 0) {
        int parent = (k - 1) >>> 1;
        Object c = es[parent];

        if(comparator.compare(x, (T) c) >= 0)
            break;

        es[k] = c;
        k = parent;
    }
    es[k] = x;
}

 

 

 

참고. 데이터 추가시 size 초과할 경우

grow() method 호출하여 queue의 길이를 증가시키고, 데이터를 복사하게 된다 (생략)

 

---

poll() - 데이터 꺼내기 

우선 순위 큐에서 데이터를 꺼낼 경우 아래의 절차를 수행한다

① root 노드 값을 꺼낸다

② 마지막 인덱스에 위치한 값을 꺼내, root 노드에 넣는다

③ 하향식으로 자식 노드와 비교하여 heapify를 수행한다 (비교할 자식 노드가 없을 때까지)

 

구현해 볼 메소드는 아래와 같다

public E poll() {
   // ..
}

// Comparator가 없는 경우
// k : 루트노드(0 고정), x : 마지막 인덱스 값, n = 현재 사이즈 - 1
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
   // ..
}

// Comparator가 주어지는 경우
private static <T> void siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
   // ..
}

 

 

poll() 구현

절차대로 root 노드(0번) 값을 꺼낸 후 마지막 인덱스에 위치한 값을 root 노드로 이동시켜 heapify를 수행하게 된다

public E poll() {
    final Object[] es = this.queue;
    final E result;

    if((result=(E)es[0]) != null) {
        final int n = --this.size;
        final E e = (E) es[n];
        es[n] = null;

        if(this.comparator == null)
            siftDownComparable(0, e, es, n);
        else
            siftDownUsingComparator(0, e, es, n, this.comparator);
    }

    return result;
}

 

 

siftDownComparable(..) 구현

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    int half = n >>> 1;
    while(k < half) {
        int child = (k << 1) + 1; // 왼쪽 자식 인덱스
        Object c = es[child];
        int right = child + 1; // 오른쪽 자식 인덱스

        // 자식이 둘 다 있을 경우
        if(right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0) {
            c = es[child = right];
        }

        if(key.compareTo((T) c) <= 0)
          break;

        es[k] = c;
        k = child;
    }
    es[k] = x; // 최종 k 위치에 x가 들어간다
}

 

① int half = n >>> 1

- shift operator의 경우 오른쪽 1비트 이동하는데,  1/2한 값과 같다 (n = 4인 경우 half = 2가 된다)

- 예로 n = 4 (노드 개수)인 경우, 2번 노드 부터 leaf 노드, 즉 자식 노드가 없게 되므로 탐색 범위가 좁혀지게 된다

- 노드 수의 절반만큼 범위를 좁혀 효율성을 개선한 것으로 파악된다

 

② if(right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0) { .. }

오른쪽 자식 노드가 존재하는 경우, 왼쪽과 오른쪽 노드의 우선 순위를 비교하여 값을 갱신한다

 

③ if(key.compareTo((T) c) <= 0)

루트 노드의 값과 자식 노드(c) 값의 우선순위를 비교하여 만족하지 않는 경우 break, 만족하는 경우 swap 하게 된다

 

- 자식이 하나만 있는 경우, 둘 다 있는 경우를 조건식으로 깔끔하게 처리하는 부분이 인상깊었다
- siftDownUsingComparable(..) 은 주입받은 comparator 사용하는 것 외에 동일하므로 생략

---

테스트 출력 

최소힙 (오름차순)

 public static void main(String[] args) {
        MyPriorityQueue<Integer> asc = new MyPriorityQueue<>(); // 오름차순, 최소힙
        asc.add(5);
        asc.add(4);
        asc.add(3);
        asc.add(2);
        asc.add(1);

        System.out.println(Arrays.toString(asc.toArray())); [1 2 4 5 3]
        System.out.println(asc.poll()); // 1
        System.out.println(asc.poll()); // 2
        System.out.println(asc.poll()); // 3
        System.out.println(asc.poll()); // 4
        System.out.println(asc.poll()); // 5
}

 

 

최대힙 (내림차순)

 public static void main(String[] args) {
    Practice<Integer> desc = new Practice<>((a, b) -> b - a); // 내림차순
    desc.add(1);
    desc.add(2);
    desc.add(3);
    desc.add(4);
    desc.add(5);

    System.out.println(Arrays.toString(desc.toArray())); // [5 4 2 1 3]

    System.out.println(desc.poll()); // 5
    System.out.println(desc.poll()); // 4
    System.out.println(desc.poll()); // 3
    System.out.println(desc.poll()); // 2
    System.out.println(desc.poll()); // 1
}

---

회고

자바 스크립트로 알고리즘 공부할 때 우선 순위 큐 라이브러리를 분석했던 적이 있었다

 

그때도 Comparator를 사용하는 구현 방식이 조건문 간소화 시켜 상당히 인상 깊었는데, 

자바에서도 동일하게 구현한 코드를 보니 똑똑한 사람은 생각하는게 비슷한가 싶다

 

자료 구조를 복습하면서 기억을 기록하기 위해 적는 거지만 

"내가 보기 편한 글"을  작성하다보니 "남이 보기 편한 글"을 작성하지는 못한거 같다

 

아직 이른 단계 일수도 있고

느리더라도 꾸준히 조금씩 개선하다보면 

언젠가 좋은 글을 작성할 거라 생각하고 

계속 하는 수 밖에 없지 않나 싶다