[자료구조] 12. 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

힙(Heap) 자료구조를 기반으로 구현된다. 힙은 노드를 활용하여 링크드리스트 처럼 구현하는 방식이 있고 배열을 활용하는 방식이 있는데 힙의 특성상 배열을 이용하는 것이 훨씬 구현이 편리하다.

 

우선순위 큐는 힙의 특성을 이용해서 '우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조'이다. 우선순위 큐에서 사용하는 힙의 특성은 '부모 노드는 항상 자식보다 우선순위가 높다'는 성질이다. 이를 활용하여 힙에서는 부모노드를 제거해가면서 우선 순위가 높은 순대로 뽑혀 나오는 것으로 구현했었다.

 

다만 주의해야할 것은 우선순위 큐가 힙이고 힙이 우선순위 큐는 아니라는 것이다. 힙은 '최솟값 혹은 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료 구조'이다. 힙의 중점은 최솟값, 최댓값 빠르게 찾기인 반면에 우선순위 큐는 우선순위가 높은 순서대로 요소를 제공받는다는 점이다. 비슷한 말 같지만 다시 정리해보자.

 

리스트 자료구조를 생각해보자. 리스트는 배열을 이용한 ArrayList, 노드간의 연결을 활용한 LinkedList로 구현했었다. 이 두개는 다르더라도 리스트 인터페이스로 구현된 리스트 구현체이다. 즉, ArrayList와 LinkedList 둘다 리스트라는 추상적인 자료구조 모델을 활용하여 구현 방식은 달리 선택한 것이다. 

 

마찬가지로 우선순위 큐는 리스트와 같이 추상적인 개념에 더 가깝다. 우선순위 큐를 구현하기 위한 많은 방법들 중에 힙을 사용한 것 뿐이다. 

 

우선순위 큐를 이제 구현해 볼건데, 어떻게 구현해나가야 할까? 힙에서는 최소, 최댓값을 찾기 위해 '부모 노드는 자식 노드보다 우선순위가 항상 높다'는 특성을 가지고 이 조건을 만족시키며 완전이진트리 형태로 채워나간다. 이는 힙 내의 요소들이 조건에 맞춰 삽입, 삭제가 될때마다 이뤄지는 동작으로 인해 구현이 된다. 자세한 것은 Heap 포스팅을 보면 된다. 이제 구현을 통해 확인해보자. 

 

---

Heap을 이용한 Priority Queue 구현

<필수 목록>

• 클래스 및 생성자, 필수 메소드 구성
• resize 메소드
• offer(=add) 계열 메소드
• poll(=remove) 계열 메소드
• size, peek, isEmpty, toArray 메소드

 

<부가 목록>

• toArray, clone 메소드

 

---

Priority Queue 클래스 및 생성자 구성

 

public class PriorityQueue<E> implements Queue<E> {

    private final Comparator<? super E> comparator;
    public static final int DEFAULT_CAPACITY = 10;

    private int size;
    private Object[] array;

    public PriorityQueue() {
        this(null);
    }

    public PriorityQueue(Comparator<? super E> comparator) {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.comparator = comparator;
    }

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

    public PriorityQueue(int capacity, Comparator<? super E> comparator) {
        this.array = new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }

    private int getParent(int index) {
        return index / 2;
    }
    
    private int getLeftChild(int index) {
        return index * 2;
    }

    private int getRightChild(int index) {
        return index * 2 + 1;
    }
}

 

---

resize 메소드 

/**
 * @param newCapacity 새로운 용량 크기
 */
private void resize(int newCapacity) {
    Object[] newArray = new Object[newCapacity];

    for (int i = 1; i <= size; i++) {
        newArray[i] = array[i];
    }

    this.array = null;
    this.array = newArray;
}

반복문을 1부터 시작하는 이유는 부모 노드 인덱스 기준 자식 노드를 찾을때 곱 연산으로 찾기 때문에 편의상 1부터 시작하기 때문이다.

 

---

offer 메소드

힙에서는 add 였으나 우선순위 큐는 Queue 인터페이스를 구현해야 하므로 offer 로 구현한다. 우선순위 큐의 삽입은 두 가지로 나뉜다.

 

1. 사용자가 Comparator를 사용하여 정렬 방법을 PriorityQueue 생성단계에서 넘겨 받은 경우 (Comparator가 null 이 아닌 경우)

2. 클래스 내에 정렬 방식을 Comprable로 구현했거나 기본 정렬 방식을 따르는 경우 (comparator가 null 인 경우)

 

 

힙의 add 와 같이 sift-up (상향 선별) 과정을 거쳐 재배치를 통해 offer를 진행한다. 값을 추가할 때 size + 1 위치에 삽입하고 부모노드, 자식노드간 대소 비교를 통해 sift-up을 진행한다.

 

@Override
public boolean offer(E item) {

    if (size + 1 == array.length) {
        resize(array.length * 2);
    }

    siftUp(size + 1, item);
    size++;

    return true;
}

/**
 * @param idx   추가할 노드의 인덱스
 * @param target    재배치할 노드
 */
private void siftUp(int idx, E target) {
    if (comparator != null) {
        siftUpComparator(idx, target, comparator);
    } else {
        siftUpComparable(idx, target);
    }
}

@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
    while (idx > 1) {
        int parent = getParent(idx);
        Object parentVal = array[parent];

        if (comp.compare(target, (E) parentVal) >= 0) {
            break;
        }

        array[idx] = parentVal;
        idx = parent;
    }

    array[idx] = target;
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {

    Comparable<? super E> comp = (Comparable<? super E>) target;

    while (idx > 1) {
        int parent = getParent(idx);
        Object parentVal = array[parent];

        if (comp.compareTo((E) parentVal) >= 0) {
            break;
        }

        array[idx] = parentVal;
        idx = parent;
    }

    array[idx] = comp;
}

 

---

poll 메소드

 

삭제는 offer와 정반대로 구현된다. 다음 그림과 코드를 보고 이해해보자.

 

 

offer를 하고난 뒤엔 sift-up(상향선별) 과정을 거쳤는데 poll은 반대로 sift-down(하향선별) 과정을 거친다.

 

@Override
public E poll() {
    if (array[1] == null) {
        return null;
    }
    return remove();
}

@SuppressWarnings("unchecked")
public E remove() {
    if (array[1] == null) {
        throw new NoSuchElementException();
    }
    E result = (E) array[1];
    E target = (E) array[size];

    array[size] = null;
    size--;
    siftDown(1, target);

    return result;
}

/**
 * 하향 선별
 * 
 * @param idx   삭제할 노드 인덱스 
 * @param target    재배치할 노드
 */
private void siftDown(int idx, E target) {
    if (comparator != null) {
        siftDownComparator(idx, target, comparator);
    } else {
        siftDownComparable(idx, target);
    }
}

@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
    array[idx] = null;

    int parent = idx;
    int child;

    while ((child = getLeftChild(parent)) <= size) {
        int right = getRightChild(parent);
        Object childVal = array[child];

        /**
         * 오른쪽 자식 인덱스가 size 를 넘지 않으면서 왼쪽 자식이 오른쪽 자식보다 큰 경우
         * 재배치할 노드는 작은 자식과 비교해야 하므로 child 와 childVal 을 오른쪽 자식으로 바꾼다.
         */
        if (right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
            child = right;
            childVal = array[child];
        }

        if (comp.compare(target, (E) childVal) <= 0) {
            break;
        }

        array[parent] = childVal;
        parent = child;
    }

    array[parent] = target;

    if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
        resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
    }
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
    Comparable<? super E> comp = (Comparable<? super E>) target;

    array[idx] = null;

    int parent = idx;
    int child;

    while ((child = (parent << 1)) <= size) {
        int right = child + 1;
        Object c = array[child];

        if (right <= size && ((Comparable<? super E>) c).compareTo((E) array[right]) > 0) {
            child = right;
            c = array[child];
        }

        if (comp.compareTo((E) c) <= 0) {
            break;
        }

        array[parent] = c;
        parent = child;
    }

    array[parent] = comp;

    if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
        resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
    }
}

---

size, peek, isEmpty, contains, clear

public int size() {
    return this.size;
}

@Override
@SuppressWarnings("unchecked")
public E peek() {
    if (array[1] == null) {
        throw new NoSuchElementException();
    }
    return (E) array[1];
}

public boolean isEmpty() {
    return size == 0;
}

public boolean contains(Object value) {
    for (int i = 1; i <= size; i++) {
        if (array[i].equals(value)) {
            return true;
        }
    }
    return false;
}

public void clear() {
    for (int i = 0; i < array.length; i++) {
        array[i] = null;
    }
    size = 0;
}

 

---

<부가 목록>

 

toArray, clone

 

1. toArray()

public Object[] toArray() {
    return toArray(new Object[size]);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length <= size) {
        return (T[]) Arrays.copyOfRange(array, 1, size + 1, a.getClass());
    }
    System.arraycopy(array, 1, a, 0, size);
    return a;
}

 

2. clone()

 

 

@Override
public Object clone() {
    try {
        PriorityQueue<?> cloneHeap = (PriorityQueue<?>) super.clone();
        cloneHeap.array = new Object[size + 1];

        System.arraycopy(array, 0, cloneHeap.array, 0 , size + 1);
        return cloneHeap;
    } catch (CloneNotSupportedException e) {
        throw new AssertionError(e);
    }
}

---

전체 코드

package Z_DataStructure.PriorityQueue;

import Z_DataStructure.A_InterfaceForm.QueueInterface;

import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

public class PriorityQueue<E> implements QueueInterface<E>, Cloneable {

    private final Comparator<? super E> comparator;
    public static final int DEFAULT_CAPACITY = 10;

    private int size;
    private Object[] array;

    public PriorityQueue() {
        this(null);
    }

    public PriorityQueue(Comparator<? super E> comparator) {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.comparator = comparator;
    }

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

    public PriorityQueue(int capacity, Comparator<? super E> comparator) {
        this.array = new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }

    /**
     * @param newCapacity 새로운 용량 크기
     */
    private void resize(int newCapacity) {
        Object[] newArray = new Object[newCapacity];

        for (int i = 1; i <= size; i++) {
            newArray[i] = array[i];
        }

        this.array = null;
        this.array = newArray;
    }

    private int getParent(int index) {
        return index / 2;
    }

    private int getLeftChild(int index) {
        return index * 2;
    }

    private int getRightChild(int index) {
        return index * 2 + 1;
    }

    @Override
    public boolean offer(E item) {

        if (size + 1 == array.length) {
            resize(array.length * 2);
        }

        siftUp(size + 1, item);
        size++;

        return true;
    }

    /**
     * @param idx   추가할 노드의 인덱스
     * @param target    재배치할 노드
     */
    private void siftUp(int idx, E target) {
        if (comparator != null) {
            siftUpComparator(idx, target, comparator);
        } else {
            siftUpComparable(idx, target);
        }
    }

    @SuppressWarnings("unchecked")
    private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
        while (idx > 1) {
            int parent = getParent(idx);
            Object parentVal = array[parent];

            if (comp.compare(target, (E) parentVal) >= 0) {
                break;
            }

            array[idx] = parentVal;
            idx = parent;
        }

        array[idx] = target;
    }

    @SuppressWarnings("unchecked")
    private void siftUpComparable(int idx, E target) {

        Comparable<? super E> comp = (Comparable<? super E>) target;

        while (idx > 1) {
            int parent = getParent(idx);
            Object parentVal = array[parent];

            if (comp.compareTo((E) parentVal) >= 0) {
                break;
            }

            array[idx] = parentVal;
            idx = parent;
        }

        array[idx] = comp;
    }

    @Override
    public E poll() {
        if (array[1] == null) {
            return null;
        }
        return remove();
    }

    @SuppressWarnings("unchecked")
    public E remove() {
        if (array[1] == null) {
            throw new NoSuchElementException();
        }
        E result = (E) array[1];
        E target = (E) array[size];

        array[size] = null;
        size--;
        siftDown(1, target);

        return result;
    }

    /**
     * 하향 선별
     *
     * @param idx   삭제할 노드 인덱스
     * @param target    재배치할 노드
     */
    private void siftDown(int idx, E target) {
        if (comparator != null) {
            siftDownComparator(idx, target, comparator);
        } else {
            siftDownComparable(idx, target);
        }
    }

    @SuppressWarnings("unchecked")
    private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
        array[idx] = null;

        int parent = idx;
        int child;

        while ((child = getLeftChild(parent)) <= size) {
            int right = getRightChild(parent);
            Object childVal = array[child];

            /**
             * 오른쪽 자식 인덱스가 size 를 넘지 않으면서 왼쪽 자식이 오른쪽 자식보다 큰 경우
             * 재배치할 노드는 작은 자식과 비교해야 하므로 child 와 childVal 을 오른쪽 자식으로 바꾼다.
             */
            if (right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
                child = right;
                childVal = array[child];
            }

            if (comp.compare(target, (E) childVal) <= 0) {
                break;
            }

            array[parent] = childVal;
            parent = child;
        }

        array[parent] = target;

        if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
            resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
        }
    }

    @SuppressWarnings("unchecked")
    private void siftDownComparable(int idx, E target) {
        Comparable<? super E> comp = (Comparable<? super E>) target;

        array[idx] = null;

        int parent = idx;
        int child;

        while ((child = (parent << 1)) <= size) {
            int right = child + 1;
            Object c = array[child];

            if (right <= size && ((Comparable<? super E>) c).compareTo((E) array[right]) > 0) {
                child = right;
                c = array[child];
            }

            if (comp.compareTo((E) c) <= 0) {
                break;
            }

            array[parent] = c;
            parent = child;
        }

        array[parent] = comp;

        if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
            resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
        }
    }

    public int size() {
        return this.size;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E peek() {
        if (array[1] == null) {
            throw new NoSuchElementException();
        }
        return (E) array[1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(Object value) {
        for (int i = 1; i <= size; i++) {
            if (array[i].equals(value)) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        size = 0;
    }

    public Object[] toArray() {
        return toArray(new Object[size]);
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length <= size) {
            return (T[]) Arrays.copyOfRange(array, 1, size + 1, a.getClass());
        }
        System.arraycopy(array, 1, a, 0, size);
        return a;
    }

    @Override
    public Object clone() {
        try {
            PriorityQueue<?> cloneHeap = (PriorityQueue<?>) super.clone();
            cloneHeap.array = new Object[size + 1];

            System.arraycopy(array, 0, cloneHeap.array, 0 , size + 1);
            return cloneHeap;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError(e);
        }
    }
}

---

정리

개인적으로 PriorityQueue와 Heap을 이번에야 제대로 다뤄본 것 같다. PriorityQueue가 Heap으로 구현할 수 있다는 것도 처음 알았고 Heap의 특성도 처음 알게 되었다. 내부 배열을 트리형태로 만들어 뽑혀 나올때 우선순위대로 나올 수 있도록 구현한 것이 정말 처음 이런 구조를 생각해낸 사람이 정말 신기하게 느껴진다.