[Java] 우선순위 큐(Priority Queue) 활용 예제코드

자바에서 제공하는 컨테이너(Container) 중 어떤 데이터에 대해 우선순위 값을 부여하고, 이 우선순위를 기준으로 자동으로 정렬되어, 우선순위에 따라 데이터를 꺼내어 사용할 수 있는 우선순위 큐에 대한 예제 코드를 정리합니다.

먼저 우선순위 값을 갖는 데이터에 대한 타입 정의가 필요합니다. 아래처럼 Node라는 클래스를 추가해 타입을 정의합니다.

package tstPriorityQueue;

public class Node implements Comparable<Node> {
	private String UUID;
	private String parentUUID;
	private double G;
	private double H;
	
	public Node(String UUID, double G, double H) {
		this.UUID = UUID;
		this.parentUUID = null;
		this.G = G;
		this.H = H;
	}
	
	public double getF() { return G + H; }
	public double getG() { return G; }
	public double getH() { return H; }
	public String getNode() { return UUID; }
	public String getParentNode() { return parentUUID; }
	
	public void setG(double v) { G = v; }
	public void setH(double v) { H = v; }
	public void setParentNode(String v) { parentUUID = v; }
	
	@Override
	public int compareTo(Node target) {
	    if (this.getF() > target.getF()) {
            return 1;
        } else if (this.getF() < target.getF()) {
            return -1;
        }

	    return 0;
	}
	
	public String toString() {
		return UUID + '(' + getF() + ')';
	}
}

위의 클래스에서 중요한 부분은 우선순위값을 얻기 위한 getF() 함수입니다. 이 함수는 데이터의 상대적인 크기의 비교를 위한 인터페이스인 Comparable 구현할 때 사용되는 함수인데요. 바로 compareTo 라는 함수로써, 위의 경우에는 우선순위값이 작은 것을 먼저 꺼내어 사용하겠다는 정의입니다.

실제로, 위의 Node 클래스에 대한 타입으로 정의된 데이터를 컨테이너에 넣고, 사용하는 코드는 아래와 같습니다.

package tstPriorityQueue;

import java.util.PriorityQueue;

public class EntryMain {

	public static void main(String[] args) {
		// Create items
		Node node1 = new Node("423182c4-edb5-11e6-bc64-92361f002671", 1.0, 5.1);
		Node node2 = new Node("42318742-edb5-11e6-bc64-92361f002671", 1.0, 2.4);
		Node node3 = new Node("42318878-edb5-11e6-bc64-92361f002671", 1.0, 3.8);
		Node node4 = new Node("42318968-edb5-11e6-bc64-92361f002671", 1.0, 6.2);
		Node node5 = new Node("42318a3a-edb5-11e6-bc64-92361f002671", 1.0, 4.5);
		
		// Create priority queue
		PriorityQueue<Node> pQueue = new PriorityQueue<Node>();
		
		// Add items to queue
		pQueue.offer(node1); // same code as pQueue.add(node1)
		pQueue.offer(node2);
		pQueue.offer(node3);
		pQueue.offer(node4);
		pQueue.offer(node5);
		
		// Get items from queue
		while(!pQueue.isEmpty()) {
			Node node = pQueue.poll();
			System.out.println(node);
		}
	}

}

데이터를 5개 생성해서, 우선순위 큐 저장소에 저장하고 최종적으로 26번 코드를 통해 5개의 데이터를 우선순위에 따라 꺼내어 화면에 표시합니다. 그 결과는 아래와 같습니다.

42318742-edb5-11e6-bc64-92361f002671(3.4)
42318878-edb5-11e6-bc64-92361f002671(4.8)
42318a3a-edb5-11e6-bc64-92361f002671(5.5)
423182c4-edb5-11e6-bc64-92361f002671(6.1)
42318968-edb5-11e6-bc64-92361f002671(7.2)