자바를 이용한 힙 정렬과 우선순위 큐 구현

힙은 데이터를 입력(offer)하면 자동으로 우선순위에 따라 정렬해주는 자료구조이다.
우선순위 큐(PriorityQueue)는 이러한 힙을 이용하여 구현한 자료구조이다.
일반적으로 Queue라는 자료구조는 '선입선출(FIFO)'의 대기열 규칙을 가지고 있는데,
우선순위 큐(PriorityQueue)는 우선순위를 결정하여 들어온 순서와 상관없이 그 우선순위가 높은 엘리먼트가 나가게된다(poll).

<자바 힙 구현>

public class my_heap {
	public static void main(String[] args) {
	    int[] array = { 30, 12, 250, 332, 25, 88, 420, 111, 219 };
	 
	    heapSort(array);
	 
	    for (int v : array) {
	        System.out.println(v);
	    }
	}
	 
	public static void maxHeapify(int array[], int length, int i) {
	    int parent = i;
	    int leftChild = i * 2 + 1;
	    int rightChild = i * 2 + 2;
	    
	    if (leftChild < length && array[parent] < array[leftChild]) { // 왼쪽 자식 값이 부모 값보다 클 경우
	        parent = leftChild; //부모 index에 왼쪽 자식 index 할당
	    }
	 
	    if (rightChild < length && array[parent] < array[rightChild]) { // 오른쪽 자식 값이 부모 값보다 클 경우
	        parent = rightChild; //부모 index에 오른쪽 자식 index 할당
	    }
	 
	    if (i != parent) {
	        swap(array, parent, i);
	        maxHeapify(array, length, parent);
	    }
	}
	 
	public static void heapSort(int[] array) {
	    int length = array.length - 1; /* index 이므로 -1 해야 함 */
	 
	    /* 주어진 데이터로 max heap을 만든다. Root 노드 방향으로 거슬러 올라감
	                마지막 노드의 부모 노드에서부터 시작 */
	    for (int i = length / 2; i >= 0; i--) {
	    	maxHeapify(array, length, i);
	    }
	
	    for (int i = length; i > 0; i--) { /* 원소가 하나 남을 때 까지 반복 */
	        swap(array, 0, i); /* 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다. for문을 돌면서 배열 뒤에서부터 차곡차곡 오름차순으로 쌓임 */
	        maxHeapify(array, i, 0); /* Root 노드 heapify */
	    }
	}
	 
	public static void swap(int[] array, int i, int k) {
	    int temp = array[i];
	    array[i] = array[k];
	    array[k] = temp;
	}
}


<우선순위 큐 예제>

자바의 PriorityQueue을 이용하면 비교 기준을 정해서 간단하게 우선순위 큐를 구현할 수 있다.
 

import java.util.Collections;
import java.util.PriorityQueue;
public class my_priorityQueue {
	private static PriorityQueue<Prisoner> getPriorityQueue() {
		Prisoner prisoner1 = new Prisoner("james", 5);
	    Prisoner prisoner2 = new Prisoner("schofield", 99);
	    Prisoner prisoner3 = new Prisoner("alex", 14);
	    Prisoner prisoner4 = new Prisoner("silvia", 10);
	    Prisoner prisoner5 = new Prisoner("thomson", 1);
	    
	    PriorityQueue<Prisoner> priorityQueue = new PriorityQueue<Prisoner>();
	    
	    priorityQueue.offer(prisoner1);
	    priorityQueue.offer(prisoner2);
	    priorityQueue.offer(prisoner3);
	    priorityQueue.offer(prisoner4);
	    priorityQueue.offer(prisoner5);
	    
	    return priorityQueue;
	}
	
	public static void main(String[] args) {
		PriorityQueue<Prisoner> priorityQueue = getPriorityQueue();
		
		System.out.println("====== Normal Order ======");
		
		while (!priorityQueue.isEmpty()) {
			Prisoner prisoner = priorityQueue.poll();
			System.out.println(prisoner.name);
		}
		
//		System.out.println("====== Reversed Order ======");
//		
//		PriorityQueue<Prisoner> reversedPriorityQueue = new PriorityQueue<Prisoner>(priorityQueue.size(), Collections.reverseOrder());
//		reversedPriorityQueue.addAll(priorityQueue);
//		
//		while (!reversedPriorityQueue.isEmpty()) {
//			Prisoner prisoner = reversedPriorityQueue.poll();
//			System.out.println(prisoner.name);
//		}
	}
}
class Prisoner implements Comparable<Prisoner> {
	String name;
	int weight; //형량
	
	public Prisoner(String name, int weight) {
		super();
		this.name = name;
		this.weight = weight;
	}
	
	@Override
	public int compareTo(Prisoner target) { // 낮은 형량순으로 오름차순
		if (this.weight > target.weight) {
			return 1;
		} else if (this.weight < target.weight) {
			return -1;
		}
		return 0;
	}
}