우선순위큐(Priority Queue)

스택(Stack)은 가장 늦게 들어간 자료가 가장 빨리 나오게되는(LIFO) 구조이고 큐(Queue)는 가장 먼저 들어간 자료가 가장 빨리 나오게 되는 (FIFO) 구조를 가진다고 각 POST에서 설명했었다.

그럼 우선순위큐는 무엇일까 ?

우선순위큐는 말 그대로 큐에서 자료를 빼는데 우선순위가 높은 것부터 빼내기 위한 자료구조이다.

우선순위큐가 실생활(real worl)에서 어떤 경우에 필요할까?

 

예를들어 은행(bank)에서 업무 처리 프로세스를 기준으로 설명해보겠다.

은행에서는 일반적으로 업무 처리는 먼저온 손님부터 처리를 해준다. 

즉, 은행에 도착해서 순서표를 뽑은 순서대로 손님을  처리해주니 업무처리를 위한 프로그래밍 자료구조로 큐가 적당해 보인다.

하지만 예외가 있는데 은행장과 친분이 있거나 거금의 돈을 예금해놓은 VIP or VVIP 타이틀을 가진 사람들은 다이렉트로 별도 공간에서 업무를 처리해준다. 

이 외에도 응급실에 환자들이 있는데 의사들은 어떤 순서로 환자를 치료해야 할까?

 

▲ [출처] http://truemiller.com/add-items-priority-queue-print-ordered-java/

 

당연히 현재 환자의 상태가 심각한지 아닌지 판단해서 우선순위 높은 순서대로 환자를 치료해야 될 것이다.

만약 이런경우를 프로그래밍 한다면 큐는 선택사항에서 적절해 보이지 않아 보인다.

 

이렇게 우선순위가 있는 경우를 먼저 처리하기 위해 나온 자료구조가 우선순위큐인데 큐와 다른점은 우선순위를 결정하기위한 키값이 존재하고 그 키값을 기준으로 정렬되어 있다.

 

우선순위를 대충 구현할 방법은 일반 Queue 자료구조에 우선순위가 높은 것이 필요하면 뒤에다 추가하지 않고 맨 앞에다가 추가하는 방식으로 하면되는데 최우선순위만 있는것이  아닌 상황에 따라 우선순위를 레벨(level-1, level-2... level-n) 로 나눈다면  이미 큐에 추가 된 것 중에서  맨 앞이 아닌  중간중간에 껴 들어가야 하는 문제가 발생하여 자료저장 구현이 여간 어려워 지는게 아니다.

 

그럼 우선순위 레벨에 따라 추가될때 알아서 정렬되는 상태로 들어가는 자료구조를 찾아야 하는데 힙(Heap)이 그 역할을 잘 수행해 낸다.

원래 힙은 데이터 원소 중에서 최대값(MAX) 및 최소값(MIN)을 찾아내는 연산을 빠르게 하기 위해 고안된 것인데  우선순위큐(Priority Queue), 힙정렬(Heap Sort), 압축 알고리즘인 허프만 코드(Huffman Code) 에도 응용되기 때문에 잘 알아 두어야 한다고 했었다.

 

사실 힙을 구현할 줄 알면 큐를 구현하는건 매우 쉽다.

자바에서 제공하는 PriorityQueue  클래스도 내부적으로는 힙을 이용해 구현되어 있다.

별도로 구현할 필요는 없지만 이전에 힙(Heap) 에서 사용했었던 코드를 재활용해서 우선순위큐를 구현하고 은행 업무 프로그래밍을 작성해보자. 

코드의 내용은 힙과 동일하므로 힙 POST를 반드시 읽기를 바란다.

 

 
import java.util.Comparator;
 
public class PriorityQueue <Key> {
    
    // 이진힙을 구성 할 때 노드를 포인터(참조)로 연겷지 않고 배열에 저장하기 위한 변수
    private Object[] nodes;
    
    // 최대힙, 최소힙에서 부모와 자식간의 키값 비교를 위한 Comparator 변수
    private Comparator<? super Key> comparator;
 
    // 힙에 맨 마지막노드(terminal node)가 저장된 배열의 index
    private int last = -1;
 
 
    /**
     * @param comparator 부모 자식간의 키값 비교를 위한것으로 최대힙으로 정렬할지 최소힙으로 정렬할지 결정할수 있다.
     * */
    public PriorityQueue(  Comparator<? super Key> comparator) {
        this.nodes = new Object[16];
        this.comparator = comparator;
    }
 
 
    // 힙에 자료를 추가한다. 데이터 추가 알고리즘을 참고할 것.
    public boolean offer(Key x) {
        if (x == null)
            throw new NullPointerException();
 
        // 1. 힙의 끝에 새로운 노드를 생성한다
        // 2. 끝에 추가된 노드에 키값(value)을 할당(assign) 한다.
        last += 1;
        nodes[last] = x;
 
        // 3. 노드의 키값과 부모노드의 키값을 비교한다.
        int k = last;
        while (k > 0) {
            int parent = (k - 1)/2;
            Object e = nodes[parent];
            if (comparator.compare(x, (Key) e) >= 0)
                break;
 
            // 4. 노드의 키와 부모노드의 키를 비교하여 스왑(swap)이 필요한경우 swap 한다.
            nodes[k] = e;
            k = parent;
        }
        nodes[k] = x;
 
        return true;
    }
 
 
    // 힙에 자료를 제거한다.
    public Key poll() {
        if (last == -1)
            return null;
 
        // 1.루트노드를 제거한다.
        // 2.마지막 레벨의 마지막 노드를 (즉, 힙의 맨 끝에 있는 노드) 루트노드로 이동한다.
        Key result = (Key) nodes[0];
        Key x = (Key) nodes[last];
        nodes[last] = null;
        nodes[0] = x;
        --last;
 
        // 3. 루트 노드의 키값과 자식노드의 키값을 비교한다.
 
        int k = 0;
        int half = (last+1) >>> 1;
        while (k < half) {
            int child = (k << 1) + 1; // 왼쪽자식차일드.
            Object c = nodes[child];
            int right = child + 1; // 오른쪽자식노드
 
            // 4. 노드의 키와 부모노드의 키를 비교하여 스왑(swap)이 필요한경우 swap 한다.
            // 왼쪽, 오른쪽 비교하여 둘중에 오른쪽서브트리로 결정해야하는 경우임.
            if (right <= last && comparator.compare((Key) c, (Key) nodes[right]) > 0)
                c = nodes[child = right];
            if (comparator.compare(x, (Key) c) <= 0)
                break;
            nodes[k] = c;
            k = child;
        }
        nodes[k] = x;
 
        return result;
    }
}

 

은행 업무 프로그래밍에서는 아래와 같은 우선순위가 있다고 가정하고 구현 한다

은행 업무 고객 우선순위

1. 등급은 일반 고객 < 우수고객 < 최우수고객으로 나뉘고 최우수고객이 가장 우선순위가 높다.
2. 만약 등급이 같다면 고객의 나이가 많은(65세이상), 즉 연장자 우대를 가진다.
3. 등급도 같고 연장자가 아니면 먼저 순번표를 뽑은 사람이 우선순위가 높다.

 

 

public class Main {
 
 
    public static final int  LEVEL_0_GRADE = 0 ; // 일반고객
    public static final int  LEVEL_1_GRADE = 1 ; // VIP
    public static final int  LEVEL_2_GRADE = 2 ; // VVIP
 
    public static class Customer{
        private int age; // 나이
        private int number; // 순번표
        private int grade; // 고객 등급
 
        public Customer(int age, int number, int grade) {
            this.age = age;
            this.number = number;
            this.grade = grade;
 
        }
 
        @Override
        public String toString() {
            return "고객정보 [" + "나이 = " + age + "/ 순서표 = " + number +  "/ 등급 = " + grade + ']';
        }
    }
 
 
    public static void main(String[] args)  {
 
        
        PriorityQueue<Customer> pq = new PriorityQueue<>(new Comparator<Customer>() {
            @Override
            public int compare(Customer o1, Customer o2) {
 
                // 만약 등급이 같다면 고객의 나이가 많은(65세이상), 즉 연장자 우대를 가진다.
                if (o1.grade == o2.grade) {
                    if(o1.age >= 65 || o2.age >= 65) {
                        return 1;
                    }
                    // 등급도 같고 연장자가 아니면  먼저 순번표를 뽑은 사람이 우선순위가 높다.
                    return o1.number - o2.number;
                }
                else {
                    return o2.grade - o1.grade;
                }
            }
        });
 
 
        pq.offer(new Customer(25, 1, LEVEL_0_GRADE));
        pq.offer(new Customer(26, 2, LEVEL_0_GRADE));
        pq.offer(new Customer(68, 3, LEVEL_0_GRADE));
        pq.offer(new Customer(40, 4, LEVEL_1_GRADE));
        pq.offer(new Customer(35, 5, LEVEL_2_GRADE));
        pq.offer(new Customer(70, 6, LEVEL_0_GRADE));
 
        
        Customer customer = pq.poll();
        while(customer != null) {
            System.out.println(customer);
            customer = pq.poll();
        }
    }
 
}
 

 

출력

고객정보 [나이 = 35/ 순서표 = 5/ 등급 = 2]
고객정보 [나이 = 40/ 순서표 = 4/ 등급 = 1]
고객정보 [나이 = 68/ 순서표 = 3/ 등급 = 0]
고객정보 [나이 = 70/ 순서표 = 6/ 등급 = 0]
고객정보 [나이 = 25/ 순서표 = 1/ 등급 = 0]
고객정보 [나이 = 26/ 순서표 = 2/ 등급 = 0]

출력된것을 보면 등급이 높고 나이가 65세 이상이면서 순서표를 빨리 뽑은 순서로 업무처리가 되는것을 확인할 수 있다.