[알고리즘] Java로 구현하는 쉬운 우선순위 큐 (Priority Queue)

Heap 은 binary tree 형태로 값을 저장하되, 루트 노드에 max heap이면 최댓값이, min heap 이면 최솟값이 저장되는 자료구조를 말한다.

최댓값이나 최솟값을 구해야 하는 경우, heap이라는 자료구조를 사용하면 굉장히 편하게 구할 수 있다.

 

우선순위 큐는 기본 큐 구조와 달리 입력 순서가 아닌 우선순위 순서로 자료를 저장하는 자료구조를 말한다.

우선순위 큐 (Priority Queue)는 Heap을 사용하여 구현하는데 우선순위에 따른 오름차순 정렬은 Min Heap으로, 내림차순 정렬은 Max Heap으로 구현할 수 있다.

 

물론, java 에 Priority Queue 라이브러리가 있기 때문에 바로 사용할 수 있지만, 공부를 위해 라이브러리를 사용하지 않고 짜보았다.

 

먼저, Min Heap의 java 코드는 다음과 같다.

 

 

위 코드를 실행하면 실행 결과는 다음과 같다.

1 2 3 4 5 6 7 8 9 

 

Max Heap 코드는 다음과 같다.

 

실행 결과는 다음과 같다.

9 8 7 6 5 4 3 2 1