[자료구조] 힙(heap)

힙

힙(heap)이란 완전 이진 트리의 일종이며, 다른 완전 이진 트리와는 다르게 중복값이 허용된다. 우선순위 큐를 구현할 때 자주 사용되는 자료 구조이다.

삽입

1. 완전 이진 트리의 성질 때문에, 노드를 추가해도 마지막 레벨의 마지막 노드 바로 오른쪽에 삽입된다.

2. 그 이후 부모 노드와 비교하여 우선순위가 높다면 서로 위치를 바꿔준다. 제 자리를 찾을때 까지 반복한다.

삭제

1. 특이하게도 루트 노드를 먼저 삭제하고, 마지막 위치에 있는 노드를 루트로 옮긴다.
2. 루트에서 다시 자식 노드와 비교하면서 서로 위치를 바꿔준다. 제 자리를 찾을때 까지 반복한다.

예제 코드(java)

문제
최소 힙

public class BOJ1927_최소힙 {
	static int N;
	static PriorityQueue<Integer> pq = new PriorityQueue<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			int input = Integer.parseInt(br.readLine());
			if (input == 0) {
				if (pq.isEmpty()) { // 큐가 비어있으면 0 출력
					bw.write(0 + "\n");
				} else { // 큐가 비어있지 않으면 삭제&출력
					bw.write(String.valueOf(pq.poll()) + "\n");
				}

			} else { // 0이 아닌 다른 숫자 삽입
				pq.offer(input);
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}

}