<자료구조> Heap & Priority Queue

분명히 3학년 때 알고리즘 강의를 수강하면서 한번 스쳐갔던(심지어 코드를 전부 암기했었던...) 개념이긴 한데 막상 활용해서 내 코드에 적용하려니 생각이 잘 안나서 다시 한번 정리할 겸 포스팅을 하려고 한다.

 

1. Heap

Heap은 Priority Queue, Heap Sort 등을 구현하기 위해 사용되는 자료 구조로, 데이터의 정렬이나 검색 보다는 우선 순위의 있는 데이터가 무엇인지 알아내고, 삭제하는 데 좀 더 유용한 자료 구조이다. 

정보처리기사를 공부하면 계속 나오는 개념 중 하나인 Binary Search에 사용하는 Binary Tree의 형식으로 보통 많이 쓰인다. 

Binary Heap은 가장 상위 노드의 최대 값을 갖는 Max Heap 과 최소 값을 갖는 Min Heap으로 각각 구현이 가능하다.

 

 1) Max Heap:

ArrayList를 이용하여 다음과 같이 구현할 수 있다. 

Code: 

package com.choonham;

import java.util.ArrayList;

public class MaxHeapClass {
	private ArrayList<Integer> maxHeap;
	
	public MaxHeapClass() {
		maxHeap = new ArrayList<>();
		maxHeap.add(100000);
	}
	
	public void insert(int n) {
		maxHeap.add(n);
		int p = maxHeap.size() - 1;
		while (p > 1 && maxHeap.get(p / 2) < maxHeap.get(p)) {
			// 부모노드와 자식 노드의 값 교환
			int tmp = maxHeap.get(p / 2);
			maxHeap.set(p / 2, maxHeap.get(p));
			maxHeap.set(p, tmp);
			p = p / 2;
		}
	}
	
	public int delete() {
		if (maxHeap.size() <= 1)
			return 0;
		int deleteItem = maxHeap.get(1); // 삭제할 노드 = 루트노드

		maxHeap.set(1, maxHeap.get(maxHeap.size() - 1));
		maxHeap.remove(maxHeap.size() - 1);

		int pos = 1;
		while ((pos * 2) < maxHeap.size()) {
			int max = maxHeap.get(pos * 2);
			int maxPos = pos * 2;

			if (((pos * 2 + 1) < maxHeap.size()) && max < maxHeap.get(pos * 2 + 1)) {
				max = maxHeap.get(pos * 2 + 1);
				maxPos = pos * 2 + 1;
			}
			if (maxHeap.get(pos) > max)
				break;
			// 부모노드 자식노드 교환
			int tmp = maxHeap.get(pos);
			maxHeap.set(pos, maxHeap.get(maxPos));
			maxHeap.set(maxPos, tmp);
			pos = maxPos;
		}

		return deleteItem;
	}

	public ArrayList<Integer> getMaxHeap() {
		return maxHeap;
	}
	
}

 

2) Min Heap:

마찬가지로, 직접 구현하면

Code:

package com.choonham;

import java.util.ArrayList;

public class MinHeapClass {

	private ArrayList<Integer> minHeap;

	public MinHeapClass() {
		minHeap = new ArrayList<>();
		minHeap.add(0);
	}

	public void insert(int n) {
		minHeap.add(n);
		int p = minHeap.size() - 1;
		while (p > 1 && minHeap.get(p / 2) > minHeap.get(p)) {
			// 부모노드와 자식 노드의 값 교환
			int tmp = minHeap.get(p / 2);
			minHeap.set(p / 2, minHeap.get(p));
			minHeap.set(p, tmp);
			p = p / 2;
		}
	}

	public int delete() {
		if (minHeap.size() <= 1)
			return 0;
		int deleteItem = minHeap.get(1); // 삭제할 노드 = 루트노드

		minHeap.set(1, minHeap.get(minHeap.size() - 1));
		minHeap.remove(minHeap.size() - 1);

		int pos = 1;
		while ((pos * 2) < minHeap.size()) {
			int min = minHeap.get(pos * 2);
			int minPos = pos * 2;

			if (((pos * 2 + 1) < minHeap.size()) && min > minHeap.get(pos * 2 + 1)) {
				min = minHeap.get(pos * 2 + 1);
				minPos = pos * 2 + 1;
			}
			if (minHeap.get(pos) < min)
				break;
			// 부모노드 자식노드 교환
			int tmp = minHeap.get(pos);
			minHeap.set(pos, minHeap.get(minPos));
			minHeap.set(minPos, tmp);
			pos = minPos;
		}

		return deleteItem;
	}

	public ArrayList<Integer> getMinHeap() {
		return minHeap;
	}

}

 

하지만 가지고 있는 원소 중 우선순위를 나타낼 수 있는 자료 구조인 Priority Queue를 이용하여 더욱 쉽고 간단하게 Heap을 구현할 수도 있다! 

 

즉,

최대값을 우선순위로 나타낸 Queue = 최대 Heap

최소값을 우선순위로 나타낸 Queue = 최소 Heap 

 

Code: 

package com.choonham;

import java.io.IOException;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args)  throws IOException {

	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		minHeap.add(100);
		minHeap.add(20);
		minHeap.add(250);
		minHeap.add(45);
		minHeap.add(3450);
        System.out.println(minHeap.peek());  // 20
        
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(1000000, Collections.reverseOrder());
    	maxHeap.add(100);
    	maxHeap.add(20);
    	maxHeap.add(250);
    	maxHeap.add(45);
    	maxHeap.add(3450);
        System.out.println(maxHeap.peek());  // 3450
        
        
	}
	
}

Collections.reverseOrder()로 최대 Heap을 만들 수 있으며, reverseOrder는 Comparator를 인자로 받기 때문에 원한다면 자신만의 순서를 정하여 사용할 수도 있다.