자바에서 1차원 배열을 활용한 우선순위 큐 구현하기

2022 상반기 신촌 ICPC 알고리즘 캠프의 트리 강의 내용을 기반으로, 매우 기본적인 우선순위 큐 프로그램을 구현하였다.

아래는 해당 강의의 노트정리 게시글이다.

초급 9회차 트리

우선순위 큐의 작동 방식을 제대로 이해하기 위하여 만들어보았다.

아무 자료도 안 찾아보고 주먹구구식으로 구현했다. 이것보다 많이 효율적인 구현 방식을 찾게 되면 하단에 추가하겠다.

 

 

2022.07.19

• 정수만 저장하는 우선순위 큐이다.
• 정수의 크기가 클수록 우선순위가 높다.
• 커맨드를 입력해 콘솔에서 우선순위 큐를 조작할 수 있다. 1~4 중 하나를 입력해 기능을 선택하는 방식이다.
• 일단 프로그램을 처음 실행하면 최초 노드의 값을 입력받는다. 노드 하나가 들어있는 새 우선순위 큐가 생성된다. 그 뒤로는 커맨드 입력 요청이 반복된다.
• 커맨드 1은 삽입, 2는 삭제, 3은 최상위 요소 보기, 4는 프로그램 종료이다.
• 만든 함수는 모든 요소 출력(print), 새 큐 만들기(init), 삽입(push), 삭제(pop), 최상위 요소 보기(top)로 5개이다.
• 1~4 이외의 정수를 입력했을 경우에는 안내 문구가 출력되도록 하였지만, 입력값 형식 오류는 딱히 처리하지 않았다. 정수만 입력해야 한다.
• 우선순위 큐의 최대 크기는 10000으로 하였다. 10000을 초과하는 크기로 삽입을 시도할 경우에 발생하는 오류는 딱히 처리하지 않았다.
• 우선순위 큐의 모든 요소가 삭제되었을 때 삭제 커맨드를 입력하면 삭제 작업을 수행하지 않고 안내 문구만 출력되도록 하였다.
• 문제가 하나 있는데, 포화 이진 트리가 아닌 경우에 특정 노드의 존재 여부를 판단할 수 없다는 것이다. 이것은 좀 쉬었다가 해결해봐야겠다. 빈 노드에 특정 값을 넣거나 null을 넣는다면 가능할 것 같다.

 

코드

2022.07.19

//신촌 ICPC 알고리즘 캠프 초급 9회차를 바탕으로 힙(Partially Ordered Binary Tree)를 이용한 우선순위 큐 구현 연습
//수의 크기가 클수록 우선순위가 높음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int[] pq;	//우선순위 큐(인덱스는 1부터 사용)
	static int size;	//현재 사용 중인 인덱스 중 최댓값
	
	//현재 우선순위 큐를 출력하는 함수
	static void print() {
		System.out.println();
		System.out.println("--------현재 트리--------");
		
		int pow = 0;
		int index = 1;
		while(index<=size) {
			
			for(int j=0; j<Math.pow(2,pow); j++) {
				System.out.print(pq[index] + "(인덱스 " + index++ + ") ");
				if(index>size) break;
				}
			System.out.println();
			pow++;
		}
		
		System.out.println();
	}
	
	//새 우선순위 큐를 생성하는 함수
	static void init(int n) {
		pq = new int[10000];
		pq[1] = n;
		size = 1;
		print();
	}
	
	//최고 우선순위인 수를 보여주는 함수
	static void top() {
		System.out.println(pq[1]);
		System.out.println();
	}
	
	//노드를 삽입하는 함수
	static void push(int n) {
		size++;
		pq[size] = n;	//우선순위 큐의 마지막 위치에 n을 추가
		
		int cur = size;	//추가된 노드의 현재 위치를 저장할 변수
		//올바른 자리 찾아주기
		while(true) {
			//root까지 왔다면 break
			if(cur==1) break;
			//추가된 노드의 우선순위가 부모의 우선순위보다 높지 않다면 break
			if(pq[cur/2]>=n) break;
			
			//우선순위가 부모보다 높아서 이동을 해야 할 경우, 부모와의 자리를 바꿈
			int temp = pq[cur/2];
			pq[cur/2] = n;
			pq[cur] = temp;
			cur = cur/2;
		}
		
		print();
	}
	
	//노드를 삭제하는 함수
	static void pop() {
		System.out.println("가장 우선순위가 높은 " + pq[1] + "을(를) 삭제합니다.");
		pq[1] = pq[size];
		size--;
		
		int cur = 1;	//이동 중인 노드의 현재 위치를 저장할 변수
		//올바른 자리 찾아주기
		while(true) {
			//leaf까지 왔다면 break
			if(2*cur>size) break;
			
			boolean l_good = pq[cur]>=pq[2*cur];	//왼쪽 자식이 자신보다 우선순위가 낮거나 같은지 여부
			boolean r_good = pq[cur]>=pq[2*cur+1];	//오른쪽 자식이 자신보다 우선순위가 낮거나 같은지 여부
			
			int change = -1;	//자신과 자리를 바꿔야 하는 자식노드의 인덱스
			
			//자식이 왼쪽밖에 없는 경우
			if(2*cur+1>size) {
				//왼쪽 자식의 우선순위가 자신보다 높지 않은 경우 break;
				if(l_good) break;
				//왼쪽 자식의 우선순위가 자신보다 높은 경우 왼쪽 자식과 자리 교체
				else change = 2*cur;
			}
			//왼쪽 오른쪽 자식 모두 존재하는 경우
			else {
				//두 자식 모두 자신보다 우선순위가 높지 않다면 break
				if(l_good && r_good) break;
				
				//나머지 경우에는 두 자식 중 더 우선순위가 높은 것과 자리 교체
				change = 2*cur;
				if(pq[2*cur]<pq[2*cur+1]) change++;
			}
			
			//change 값을 바탕으로 자리 교체 수행
			int temp = pq[cur];
			pq[cur] = pq[change];
			pq[change] = temp;
			cur = change;
		}
		
		print();
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = -1;	//초기화, 삽입, 삭제 시 동작의 대상이 될 수를 입력받아 저장할 변수
		
		//최초 우선순위 큐 만들기
		size = 0;
		System.out.print("최초 노드의 값 입력>> ");
		n = Integer.parseInt(br.readLine());
		init(n);
		
		
		
		while(true) {
			System.out.println("1: 삽입, 2: 삭제, 3: 최상위 값 출력, 4: 프로그램 종료");
			System.out.print("커맨드 입력>> ");
			
			int command = Integer.parseInt(br.readLine());
			
			switch(command) {
			
			case 1:
				System.out.print("삽입할 노드의 값 입력>> ");
				n = Integer.parseInt(br.readLine());
				push(n);
				break;
			case 2:
				if(size==0) {System.out.println("큐가 비어있습니다"); break;}
				pop();
				break;
			case 3:
				top();
				break;
			case 4:
				System.out.print("~Good Bye~");
				System.exit(0);
			default:
				System.out.println("1과 4 사이의 정수를 입력해주십시오.");
			}
		}

	}

}