문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설명 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙이다. 최대 힙을 구현하기 위해 MaxHeap 클래스를 만들고 추가 기능과 제거 기능을 추가한다. class MaxHeap { List list; public MaxHeap() { list = new Arra..
힙 (Heap) 완전 이진 트리 형태의 자료구조 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 또한, 우선순위 큐를 구현할 때에도 힙 자료구조를 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간은 \(O(logN)\) 이다. 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다. 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다. 힙의 삽입 연산 트리의 가장 마지막 위치에 노드를 삽입한다. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다. 만족하지 않다면 부모와 자식의 키 값을 바꾼다. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2번~3번을 반복한다. 힙의 삭제 연..
우선순위 큐의 특징 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 우선순위 큐를 사용하기 위해서는 Comparable 인터페이스 또는 Comparator 인터페이스를 재정의해야 한다. 각각 compareTo 메소드와 compare 메소드를 재정의해야 되는데 거기서 우선순위 조건을 리턴해주면 우선순위 큐에서 알아서 우선순위대로 정렬해준다. 우선순위 큐는 일반적으로 힙을 이용하여 구현한다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭..
