Priority Queue(우선순위 큐)

최근 알고리즘 문제를 한개씩 풀다보면 풀다보면 자주 최대 힙, 최소 힙을 구현하여 사용해야 되는 경우가 생깁니다.

(예를 들면 위상정렬, 최대값 뽑아내기 등)

 

자바에서는 현재  PriorityQueue를 이용하여 최대 힙, 최소 힙을 간단하게 사용할 수 있도록 제공해주고 있습니다. 

 

다음은 최대 힙, 최소 힙에 대한 간단한 예시입니다.

public void init()  throws IOException{
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    System.out.println("최소 힙");
    runHeapTest(minHeap);

	
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    System.out.println("최대 힙");
    runHeapTest(maxHeap);
}
	
private void runHeapTest(PriorityQueue<Integer> heap) {
	heap.add(1);
	heap.add(8);
	heap.add(5);
	heap.add(2);
	heap.add(3);
	while(!heap.isEmpty()) {
    	System.out.println(heap.poll());
    }
}

해당 결과는 다음과 같이 노출 됩니다.

 

위에 코드블럭에 대한 결과 사진

 

하지만 보통 알고리즘을 풀다보면 이런 간단한 Integer값이 아니라 여러개의 값을 비교하여 최대, 최소를 구하라는 요구가 주어지고, 이를 위해서는 Object를 생성하여 추가를 해야합니다. 이럴 경우 Comparable 또는 Comparator를 구현하여 생성한 Class(Object)를 PriorityQueue에서 사용할 수 있습니다.

 

간단한 예시로서 Rastaurant 라는 class에 Comparable를 Implement를 한 다음 출력을 위한 toString, compareTo를 구현합니다. 그리고 위의 코드블럭에서 heap add 부분을 클레스로 add되도록 수정했습니다.

class Restaurant implements Comparable<Restaurant>{
	int grade;
	int distance;
	
	public Restaurant(int grade, int distance) {
		this.grade = grade;
		this.distance = distance;
	}
	
	public String toString() {
		return "grade : "+this.grade +" and distance :"+this.distance;
	}

    @Override
    public int compareTo(Restaurant target) {
    	if(this.grade == target.grade) {
    		return this.distance <= target.distance ? -1 : 1;
    	}
    	else {
    		return this.grade <= target.grade ? -1 : 1;
    	}
    }
}


------------------------------------------
public void init()  throws IOException{
	PriorityQueue<Restaurant> minHeap = new PriorityQueue<>();
    System.out.println("최소 힙");
    runHeapTest(minHeap);
    
    PriorityQueue<Restaurant> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    System.out.println("최대 힙");
    runHeapTest(maxHeap);
}
	
private void runHeapTest(PriorityQueue<Restaurant> heap) {
	heap.add(new Restaurant(1, 5));
	heap.add(new Restaurant(1, 4));
	heap.add(new Restaurant(2, 5));
	heap.add(new Restaurant(4, 3));
	heap.add(new Restaurant(4, 5));
	while(!heap.isEmpty()) {
    	System.out.println(heap.poll().toString());
    }
}

 이 결과를 보면 다음과 같이 출력 됩니다.

최대힙 최소힙 변경결과

위에 @Override된 결과문에서 (return this.distance <= target.distance ? -1 : 1;)

해당부분에 더 작으면 -1 (우선순위 업), 크면 1(우선순위 다운)을 리턴하는 결과를 가지고 priorityQueue가 동작하게 됩니다. (Collections.reverseOrder() 선언은 반대)

 

만약 코드상에 Collections.reverseOrder() 를 선언하고 싶지않다면  Comparable에서 -1 을 1로 1을 -1로 변경해주면 최대힙의 결과를 동일하게 볼 수 있습니다.