1927번 최소 힙

문제링크 : www.acmicpc.net/problem/1927

1927번: 최소 힙

---

---

<알고리즘>

  1) 조건에 맞춰 삭제 시

      1-1) 입력값이 없을 경우  return 0

       1-2) 그외의 경우

             root위치의 요소를 임시로 저장->마지막요소를 root자리로 끌어옴(set, remove이용)

             root요소를 그 밑의 서브트리와 비교하여 작은 게 root로 오게 재정리

  2) 조건의 맞춰 입력시

      배열에 제일 마지막에 넣은뒤, 해당 요소의 parent값과 비교하여 작은 순으로 정렬(해당요소의 최대 도달지점은 1) 

 

 

메모리 : 35032KB     시간 : 1436ms     

package baekjoon;

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

public class B_1927_smallest_heap {

	public static int del(ArrayList<Integer> al) {
		if (al.size()==1) {return 0;}
		else {
			int temp = al.get(1);
			al.set(1,al.get(al.size()-1));
			al.remove(al.size()-1);
			
			int focus= 1;
			while(2*focus<al.size()) {
				int mini = al.get(focus*2);
				int minInd = focus*2;
				if(focus*2+1<al.size() && mini>al.get(focus*2+1)){
					mini = al.get(focus*2+1);
					minInd = focus*2+1;
				}
				if(al.get(focus)<mini) break;
				else {
					int ctemp = al.get(focus);
					al.set(focus, al.get(minInd));
					al.set(minInd, ctemp);
					focus = minInd;
				}
			}
			return temp;
		}
	}
	public static void in(ArrayList<Integer> al, int N) {
		al.add(N);
		int child = al.size()-1;
		int parent = (int)(child/2);
		while(child>0 && al.get(parent)>al.get(child)) {
			int temp = al.get(child);
			al.set(child, al.get(parent));
			al.set(parent, temp);
			child = parent;
			parent = (int)(parent/2);
		}
	}
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T =0;
		try {T=Integer.parseInt(bf.readLine());} catch(IOException e) {}
		
		ArrayList<Integer> al = new ArrayList<>();
		al.add(0);
		while(T!=0) {
			int N = 0;
			try {N=Integer.parseInt(bf.readLine());} catch(IOException e) {}
			if(N==0) {
				//0또는 가장 작은 수 출력
				System.out.println(del(al));
			}
			else {
				//input
				in(al,N);
				for(int i =0;i<al.size();i++) {
					System.out.print(al.get(i));
					System.out.print(" ");
				}
			}
			T--;
		}
		
	}
}