[백준 알고리즘] 1927번 최소 힙

1. Point

• Heap 자료구조 시간복잡도
  • 삽입 : 맨 마지막 Index 에 넣고, 부모 노드랑 비교. 부모 노드 비교 식은 (index -1) / 2 로 1/2 씩 비교하게 되니 logN 이 됨.
  • 삭제 : 맨 마지막 Index 를 Root 로 옮겨서, 자식 노드 2개씩 비교해가면서 내려가니 logN 이 됨.

2. Source

public static void main(String[] args)
{
 PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
 Scanner sc = new Scanner(System.in);
 int N = sc.nextInt();
 for (int idx = 0 ; idx < N ; idx++)
 {
  int x = sc.nextInt();
  if (x == 0)
  {
   if (queue.isEmpty()) 
    System.out.println(0);
   else 
    System.out.println(queue.poll());
  }
  else
  {
   queue.offer(x);
  }
 }
}