PriorityQueue

https://swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=test02&category=undefined 

SW Expert Academy

일단 트리에 대한 개념이 없으면 이해할 수 없으므로 트리부터 공부해야 함.

1. 초기화

2. data 넣기

3. data 빼기 - queue이지만 값에 따라 계속 재정렬되기 때문에 넣은 순서대로 나오지는 않음

4. data 출력 - stack과 queue처럼 main 함수 내에서 값을 삭제하는 동시에 값을 빼오면 재정렬되면서 메모리와 시간이 낭비되므로 출력되는 메소드를 따로 구현해준 것 같음.

 

package DataStructure;

import java.util.Scanner;

public class DS_PriorityQueue {
	static Scanner sc;
	
	static final int MAX_SIZE = 100;
	static int heap[] = new int[MAX_SIZE];
	static int heapSize = 0;
	
	static void heapInit() {
		heapSize = 0;
	}
	
	static void heapPush(int value) {
		if(heapSize + 1 > MAX_SIZE)
			return;
		
		heap[heapSize] = value;
		
		int current = heapSize;
		//index - 1이 0 미만이 되면 안되기 때문에 current > 0
		//트리구조로 부모노드의 index는 자식노드 (index - 1) / 2
		//부모노드가 더 크면 자리를 바꿔줌. 부모노드가 더 작을 때까지 계속 반복
		while(current > 0 && heap[current] < heap[(current - 1) / 2]) {
			int temp = heap[(current - 1) / 2];
			heap[(current - 1) / 2] = heap[current];
			heap[current] = temp;
			current = (current - 1) / 2;
		}
		
		heapSize = heapSize + 1;
	}
	
	static int heapPop() {
		//heap이 비어있으면
		if(heapSize <= 0)
			return -1;
		
		//index 0은 pop할 변수
		int value = heap[0];
		//사이즈-- 해줌
		heapSize = heapSize - 1;
		//재정렬을 위해 맨 끝의 data를 맨 앞에 저장
		heap[0] = heap[heapSize];
		
		int current = 0;
		//현재노드의 왼쪽 자식노드 index가 heapSize보다 작아야 함
		//비교할 자식이 있는 노드까지만 탐색. index가 heapSize인 노드의 data는 이미 index 0 위치에 저장되어있으므로 제외.
		while(current < heapSize && current * 2 + 1 < heapSize) {
			//부모노드와 비교할 자식노드의 index를 저장할 변수
			int child;
			//오른쪽 자식 노드 index가 heapSize보다 크거나 같으면
			//비교할 수 있는 자식이 아니기 때문에 왼쪽 노드의 index를 저장
			if(current * 2 + 2 >= heapSize) {
				//왼쪽 자식 노드 index 저장
				child = current * 2 + 1;
			}
			//오른쪽 자식 노드 index가 heapSize보다 작으면
			else {
				//왼쪽자식 data와 오른쪽자식 data중 더 작은 data를 가진 노드의 index를 저장
				//더 작은 data를 부모노드와 바꿔줘야 하기 때문
				child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
			}
			
			//현재 노드의 data가 자식노드들의 data보다 작으면 바꾸지 않고 넘어감
			if(heap[current] < heap[child])
				break;
			
			//현재 노드의 data보다 child의 data가 더 작으면 자리를 바꿔줌
			int temp = heap[current];
			heap[current] = heap[child];
			heap[child] = temp;
			
			current = child;
		}
		return value;
	}
	
	static void heapPrint(int[] heap, int heap_size) {
		for(int i = 0; i < heap_size; i++)
			System.out.print(heap[i] + " ");
		System.out.println();
	}
	
	public static void main(String[] args) throws Exception{
		sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int t = 1; t <= T; t++) {
			int N = sc.nextInt();
			
			heapInit();
			
			for(int i = 0; i < N; i++) {
				int value = sc.nextInt();
				heapPush(value);
			}
			
			System.out.print("#" + t + " ");
			
			for(int i = 0; i < N; i++) {
				System.out.print(heapPop() + " ");
			}
			System.out.println();
		}
		sc.close();
	}
}